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();
  }
}