perogram

F - Pure ~ワーシャルフロイド・最小閉路・経路復元~

Quiz

https://atcoder.jp/contests/abc142/tasks/abc142_f

Submission

https://atcoder.jp/contests/abc142/submissions/7805082

解法

補足

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

f:id:peroon:20191001042803p:plain

経路復元

VI get_path(ll i, ll j){
  VI rev(N, -1);
  vector<bool> visited(N, false);
  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;
  }
}