题目大意
给定一张 \(n\) 个点，\(m\) 条边的无向图，每条边的边权均为 \(1\)。对于每一个 \(i\in [1,m]\) 求出从点 \(1\) 到 \(n\) 的不经过第 \(i\) 条边的最短路长度。
思路分析
我们先在原图上求出从点 \(1\) 到点 \(n\) 的最短路，注意到最短路的路径长度不会超过 \(n-1\)，这是因为每个点最多出现一次。
那么对于每一条边，如果它处于原图中从点 \(1\) 到点 \(n\) 的最短路径上，我们就把这条边删掉再跑一遍最短路得出答案，否则答案就是原本的最短路长度。
求一次最短路的时间复杂度是 \(O(n+m)\) 的，所以总时间复杂度是 \(O(n^2+nm)\)，可以通过。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int N=200100;
#define inf 0x3f3f3f3f
int n,m,in1,in2;
int dis[N],vis[N],pre[N];
vector<int> to[N];
set<pair<int,int>> s;
queue<int> q;
pair<int,int> edge[N];
int bfs(int notedge){//直接 bfs 求出最短路
for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=0;
while(!q.empty()) q.pop();
q.push(1);dis[1]=0;
while(!q.empty()){
int now=q.front();q.pop();
if(vis[now]) continue;
vis[now]=1;
for(int v:to[now]){
if(edge[notedge]==make_pair(now,v)) continue;//直接跳过删除的边
if(dis[v]>dis[now]+1){
dis[v]=dis[now]+1;
q.push(v);
if(!notedge) pre[v]=now;
}
}
}
if(dis[n]==inf) return -1;
return dis[n];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&in1,&in2);
to[in1].push_back(in2);
edge[i]={in1,in2};
}
int len=bfs(0),x=n;
while(x!=1){//从 n 开始倒推
if(!pre[x]) break;
s.insert({pre[x],x});
x=pre[x];
}
for(int i=1;i<=m;i++)
if(s.count({edge[i].first,edge[i].second})) cout<<bfs(i)<<'\n';
else cout<<len<<'\n';
return 0;
}