[ABC218] F - Blocked Roads

[Q] https://atcoder.jp/contests/abc218/tasks/abc218_f

ダイクストラ。
約160000本の切断パターン全部をダイクストラするとTLEしてしまう。

頂点400なので、全道の最短経路は最大でも399本の道を通る。
160000-399の156001本の辺は、切断しようがしまいが最短経路と関係ないので、省略できる。

Q. 200010?
A. 辺の数は400*399まで入りうる。(1RE)

ll S[200010];
ll T[200010];

int main(){
 cincout();
 
 ll N, M;
 cin >> N >> M;
 graph g(N+1); // 0index ~ 
 rep(i, M){
   ll s, t;
   cin >> s >> t;
   --s;
   --t;
   S[i] = s;
   T[i] = t;
   g.add_edge(s, t, 1);
 }
 g.dijkstra(0);
 // 最短パスを出す。最短路以外の解答がこれ
 ll low = g.d[N-1];
 if (low == oo){ // そもそもNまでいけない
   rep(i, M) cout << -1 << endl;
   return 0;
 }
 vector<ll> path = g.get_path(N-1, 0); //goal, start
 bool B[410][410] = {}; // 最短路メモ
 ll sz = path.size();
 rep(i, sz-1){
   ll a=path[i];
   ll b=path[i+1];
   B[a][b] = true;
   B[b][a] = true;
 }
 rep(i, M){
   ll s=S[i];
   ll t=T[i];
   if (!B[s][t] && !B[t][s]){ // 最短路じゃない
     cout << low << endl;
     continue;
   }
   g.del_edge(S[i], T[i], 1); // バックトラックみたいな。再dijkstra
   g.dijkstra(0);
   ll ret = g.d[N-1];
   if (ret == oo) ret = -1;
   cout << ret << endl;
   g.add_edge(S[i], T[i], 1);
 }
}

https://atcoder.jp/contests/abc218/submissions/25791646