公式
F - Blocked Roads 解説 by blackyuki
元のグラフで頂点 \(1\) から頂点 \(N\) にたどり着ける場合を考えます。
まず、元のグラフでの頂点 \(1\) から頂点 \(N\) までの最短経路を \(1\) つ求めます。 この最短経路に含まれない辺については、通行止めになったとしても影響がありません。
また、最短経路に含まれる辺は高々 \(N-1\) 本です。よって、最短経路に含まれる辺が通行止めになった場合には、愚直に \(O(N+M)\) で最短距離を求めても全体としては \(O(N(N+M))\) で十分間に合います。
元のグラフで頂点 \(1\) から頂点 \(N\) にたどり着けない場合の例外処理に注意してください。
実装例 (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m; cin >> n >> m;
vector<vector<int>> G(n, vector<int>(n, -1));
vector<pair<int,int>> edge(m);
for(int i = 0; i < m; i++){
int a, b; cin >> a >> b; a--; b--;
G[a][b] = i;
edge[i] = make_pair(a,b);
}
vector<int> dis(n,-1); dis[0] = 0;
vector<pair<int,int>> memo(n);
queue<int> que; que.push(0);
while(!que.empty()){
int i = que.front(); que.pop();
for(int j = 0; j < n; j++) if(dis[j] == -1 && G[i][j] != -1){
dis[j] = dis[i] + 1;
memo[j] = make_pair(i,G[i][j]);
que.push(j);
}
}
if(dis[n-1] == -1){
for(int i = 0; i < m; i++) cout << -1 << endl;
return 0;
}
vector<int> shortest_path;
int cur = n-1;
while(cur != 0){
shortest_path.push_back(memo[cur].second);
cur = memo[cur].first;
}
vector<int> ans(m, dis[n-1]);
for(int e : shortest_path){
G[edge[e].first][edge[e].second] = -1;
queue<int> que; que.push(0);
vector<int> dis(n, -1); dis[0] = 0;
while(!que.empty()){
int i = que.front(); que.pop();
for(int j = 0; j < n; j++) if(dis[j] == -1 && G[i][j] != -1){
dis[j] = dis[i] + 1;
que.push(j);
}
}
ans[e] = dis[n-1];
G[edge[e].first][edge[e].second] = e;
}
for(int x:ans)cout << x << endl;
}
投稿日時:
最終更新: