F - Pure ～ワーシャルフロイド・最小閉路・経路(パス)復元～

• Quiz
  • https://atcoder.jp/contests/abc142/tasks/abc142_f
• Submission
  • https://atcoder.jp/contests/abc142/submissions/7805082

解法

• ワーシャルフロイドを使った最小閉路の検出
• algorithm - graph - How to find Minimum Directed Cycle (minimum total weight)? - Stack Overflow
• https://stackoverflow.com/questions/10456935/graph-how-to-find-minimum-directed-cycle-minimum-total-weight
• (この解法は想定解ではないです)

補足

• N=1000で通るのか？ギリギリ通る（事前にワーシャルフロイドだけして提出 1000msなのでギリギリ通ることを確認)
  • N=1000
  • O(N³)のワーシャルフロイド。ここが計算量のボトルネックで、実行時間は1100ms. よって10⁹は超シンプルでギリギリ通る
• uからvに行き、vからuに行くと最小のサイクル
  • そういうu, vをO(N²)の全探索で探す。見つけた後はpath(u, v), path(v, u)を求めればよい
• path(u, v)はbfsで求めた。配列revで足跡を保存
  • (変数名はpreでもいいかも)

(revを用いた)経路復元

// iからjへの経路
// N : 頂点数
// G : graph (vector<vector<int>>)
VI get_path(ll i, ll j){
  VI rev(N, -1); // どこから来たかを保存
  vector<bool> visited(N, false);

  // bfsして各頂点への最短路を求める
  queue<ll> que;
  que.push(i);
  visited[i] = true;
  while(!que.empty()){
    ll from = que.front(); que.pop();
    for(ll to : G[from]){
      if(visited[to]) continue;
      visited[to] = true;
      rev[to] = from; // どこから来たかを保存
      que.push(to);
    }
  }
  VI ret;
  ret.push_back(j); // 終点から足していく
  
  ll now = j;
  while(true){
    ret.push_back(rev[now]);
    now = rev[now];
    if(now==i) return ret;
  }
}