Google KickStart 2020H-D "Friends"
サクッと解けた。この回はずいぶん簡単だったと思う(KickStartって結構難しい問題あるんだけど...)
codingcompetitions.withgoogle.com
解法
簡単にいうと、人 i が文字xを経由して人 j に到達する、というルートを、文字xについて26通り試すと、最短ルートは必ず上記26通りのどれかにはヒットするということが言えるので、26通りのDijkstra最短経路を前計算しておくと、各QueryについてO(1)で求められます。ちょっとジャッジに時間がかかってそうで不安になりましたが、下のコードでACしました。
// solution for KickStart2020H-D // author : lynmisakura #include<bits/stdc++.h> using namespace std; using ll = long long; template<class T> struct Edge{ int from,to,id; T cost; Edge(int from,int to,T cost):from(from),to(to),cost(cost){} Edge(int from,int to,int id,T cost):from(from),to(to),id(id),cost(cost){} Edge(){} }; template<class T> struct Graph{ int n; vector<vector<Edge<T>>> g; Graph(int n):n(n){ g.resize(n); } void add_edge(int from,int to){ g[from].emplace_back(from,to,1); } void add_edge(int from,int to,T cost){ g[from].emplace_back(from,to,cost); } vector<Edge<T>>& operator[](int i){ return g[i]; } }; template<class T> struct Dijkstra{ #define INF (numeric_limits<T>::max()/2) using P = pair<T,int>; Graph<T> G; vector<T> d; vector<int> prev; Dijkstra(Graph<T>& G):G(G){} void solve(int s){ d.assign(G.n,INF); prev.assign(G.n,-1); d[s] = 0; priority_queue<P,vector<P>,greater<P> > que; que.push(P(0,s)); while(que.size()){ P p = que.top();que.pop(); int v = p.second; if(d[v] < p.first) continue; for(int i = 0;i < G[v].size();i++){ Edge<T>& e = G[v][i]; if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; prev[e.to] = v; que.push(P(d[e.to] , e.to)); } } } } bool reachable(int t){ return d[t] != INF; } vector<int> get_path(int t){ vector<int> path; for(;t != -1;t = prev[t]){ path.push_back(t); } reverse(path.begin(),path.end()); return path; } T& operator[](int i){return d[i];} }; void main2(){ int n,q;cin >> n >> q; vector<string> a(n); Graph<int> graph(n + 26); for (int i = 0; i < n; i++) { cin >> a[i]; vector<int> used_chars(26,0); for(char x : a[i]) used_chars[x - 'A']++; for (int j = 0; j < 26; j++) { if(used_chars[j]){ graph.add_edge(i,n+j,1); graph.add_edge(n+j,i,1); } } } vector<Dijkstra<int>> D(26,Dijkstra<int>(graph)); for (int i = 0; i < 26; i++) { D[i].solve(n+i); } for (int i = 0; i < q; i++) { int s,t;cin >> s >> t; s--,t--; bool reachable = false; int mindist = int(1e9); for (int j = 0; j < 26; j++) { reachable |= (D[j].reachable(s) && D[j].reachable(t)); mindist = min(mindist , D[j][s] + D[j][t]); } if(!reachable)cout << -1 << ' '; else cout << 1 + mindist / 2 << ' '; } cout << '\n'; } int main(){ cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(20); int tt;cin >> tt; for(int i=1;i<=tt;i++){ cout << "Case #" << i << ": "; main2(); } }