题意：给定一个n个点,m条边的有向图，边权为1。求把某一条边（依次从1-》m）去掉之后1到n的最短距离.
思路：这道题可以这么考虑。先求出1到N的最短路径，并记录路径。如果删掉的这条边不在最短路上，那么直接输出最短路。否则，我们暴力求出删掉边之后的最短路，判断一下即可。 时间复杂度（优先队列优化的Dij M*log(N) M约等于N^2）N^3*log(N)
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 #define int long long 6 #define pb push_back 7 const int N = 3e5+100 , inf = 6666666666; 8 int n,m; 9 struct node{ 10 int v,w; 11 bool operator <(const node &t) const 12 { 13 return w>t.w; 14 } 15 }; 16 vector<node> g[N]; 17 vector<int> v[N],p; 18 int a[N],b[N]; 19 int dis[N],vis[N],path[N]; 20 map<pair<int,int>,int >mp,mmp; 21 void dijkstra(int s){ 22 for(int i=0;i<=n;i++) dis[i]=inf,vis[i]=0; 23 dis[s]=0; 24 priority_queue<node> q; 25 q.push((node){s,0}); 26 while(!q.empty()){ 27 node t=q.top(); 28 q.pop(); 29 if(vis[t.v]) 30 continue; 31 vis[t.v]=1; 32 int u=t.v; 33 for(int i=0;i<g[u].size();i++){ 34 35 int to=g[u][i].v; 36 int w=g[u][i].w; 37 if(mmp[make_pair(u,to)]) 38 continue; 39 if(dis[to]>dis[u]+w){ 40 dis[to]=dis[u]+w; 41 path[to]=u; 42 q.push((node){to,dis[to]}); 43 } 44 } 45 } 46 return ; 47 } 48 signed main(){ 49 memset(path,-1,sizeof(path)); 50 cin>>n>>m; 51 for(int i=1;i<=m;i++){ 52 cin>>a[i]>>b[i]; 53 g[a[i]].pb((node){b[i],1}); 54 v[b[i]].pb(a[i]); 55 } 56 dijkstra(1); 57 int tot=dis[n]; 58 if(tot==inf){ 59 for(int i=0;i<m;i++) cout<<"-1"<<endl; 60 exit(0); 61 } 62 63 int tmp=n; 64 while(path[tmp]!=-1){ 65 // cout<<tmp<<" "; 66 p.pb(tmp); 67 tmp=path[tmp]; 68 } 69 p.pb(1); 70 reverse(p.begin(),p.end()); 71 // for(int i=0;i<p.size();i++) cout<<p[i]<<" ";cout<<endl; //输出路径 72 // for(int i=1;i<=n;i++) cout<<dis[i]<<" ";cout<<endl; 73 // cout<<dis[n]<<endl; 74 for(int i=1;i<p.size();i++) 75 mp[make_pair(p[i-1],p[i])]=1; 76 for(int i=1;i<=m;i++){ 77 if(!mp[make_pair(a[i],b[i])]){ 78 cout<<tot<<endl; 79 }else{ 80 mmp.clear(); 81 mmp[make_pair(a[i],b[i])]=1; 82 dijkstra(1); 83 if(dis[n]==inf) cout<<"-1";else cout<<dis[n]; 84 cout<<endl; 85 } 86 } 87 return 0; 88 }