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