linkk
题意：
给出点数为n，边数为m的有向图，问每次删去一条边时，1 − n的最短路，每次询问相互独立。n < = 400
思路：
如果要删去的边不在1到n的最短路上的话，那么不会对最短路造成影响。
如果在最短路上的话，就需要重新跑一遍最短路。
由于n只有400，时间复杂度为O ( n ∗ ( n + m ) )
具体操作为：
求出1到n的最短路r e s并且记录下最短路上的边。
对于m条边，看是否在最短路上，如果不在的话，直接输出r e s
如果在的话，重新跑一遍最短路，并且不能用到第i条边。在b f s的时候传入参数x表示不能用第x条边，如果x = = 0的话，说明全部边都可以用，在这次记录前驱。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int>PII; inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=2e5+7,inf=0x3f3f3f3f; int n,m,pre[maxn]; vector<int>g[maxn]; PII edge[maxn]; set<PII>st; int dis[maxn]; int bfs(int x){ memset(dis,0x3f,sizeof dis); queue<int>q; q.push(1);dis[1]=0; while(!q.empty()){ int t=q.front();q.pop(); if(t==n) return dis[n]; for(auto tt:g[t]){ if(edge[x].first==t&&edge[x].second==tt) continue; if(dis[tt]>dis[t]+1){ dis[tt]=dis[t]+1; if(x==0) pre[tt]=t; q.push(tt); } } } return -1; } int main(){ n=read,m=read; rep(i,1,m){ edge[i].first=read,edge[i].second=read; g[edge[i].first].push_back(edge[i].second); } int res=bfs(0); int now=n; while(now!=1){ if(!pre[now]) break; PII tmp={pre[now],now}; now=pre[now]; st.insert(tmp); } for(int i=1;i<=m;i++) if(st.count(edge[i])) printf("%d\n",bfs(i)); else cout<<res<<endl; return 0; } /* */ /**/
