题目链接：

题意：给出一个带权无向图，起点S和终点T。Q个询问。每个询问询问删除某条边后S到T的最短路。

思路：

（1）计算每个点到S和T的最短路；

（2）记录最短路用到的边，这些边构成一个新图；

（3）求出新图上的桥，桥将新图分成若干连通块（其实所有的连通块是线性排列的）；

（4）对于删除的边若不是新图中的桥无视；否则，枚举这个桥连接的两个连通块的所有边，并用这些边(u,v)的权+disS[u]+disT[v]作为排序关键字对边排序，最小的即是答案。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define pb(x) push_back(x)#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))using namespace std;struct node{ int v,next; i64 dis; node(){} node(int _v,i64 _dis) { v=_v; dis=_dis; } friend bool operator<(node a,node b) { return a.dis>b.dis; }};const i64 INF=((i64)1)<<62;const int MAXN=200005;const int MAXE=1000005;node edges[MAXE];int head[MAXN],begin[MAXN],end[MAXN],query[MAXN],e;int Qu[MAXN],Qv[MAXN];i64 disS[MAXN],disT[MAXN],ans[MAXN];int n,m,S,T,visit[MAXE];int shy[MAXN<<1],imp[MAXN<<1];int low[MAXN],dfn[MAXN],id,father[MAXN];int color[MAXN],colorNum;int go[MAXN],rank[MAXN],f[MAXE];priority_queue
              
                Q;void init(){ clr(head,-1); clr(begin,-1); clr(end,-1); clr(query,-1); clr(imp,0); clr(low,0); clr(dfn,0); clr(color,0); clr(go,0); clr(rank,0); clr(ans,-1); e=2; id=0; colorNum=0;}void Add1(int u,int v,i64 dis){ edges[e].v=v; edges[e].dis=dis; edges[e].next=head[u]; head[u]=e++;}void Dij(int s,i64 dis[]){ int i,u,v; node p,q; for(i=0;i<=n;i++) dis[i]=INF; while(!Q.empty()) Q.pop(); Q.push(node(s,0)); dis[s]=0; while(!Q.empty()) { p=Q.top(); Q.pop(); u=p.v; for(i=head[u];i!=-1;i=edges[i].next) { v=edges[i].v; if(dis[v]>p.dis+edges[i].dis) { dis[v]=p.dis+edges[i].dis; Q.push(node(v,dis[v])); } } }}void BFS(int s){ clr(shy,0); clr(visit,0); queue
               
                 Q; int i,u,v; Q.push(s); visit[s]=1; while(!Q.empty()) { u=Q.front(); Q.pop(); for(i=head[u];i!=-1;i=edges[i].next) { v=edges[i].v; if(disS[v]==disS[u]+edges[i].dis) { shy[i]=1; shy[i^1]=2; if(visit[v]) continue; Q.push(v); visit[v]=1; } } }}void DFS(int u){ color[u]=colorNum; int i,v; for(i=head[u];i!=-1;i=edges[i].next) { v=edges[i].v; if(shy[i]==1&&!color[v]) DFS(v); }}int Tarjan(int u){ int p=(u==T),i,v; dfn[u]=low[u]=++id; for(i=head[u];i!=-1;i=edges[i].next) if(shy[i]==1) { v=edges[i].v; if(!dfn[v]) { father[v]=i; if(Tarjan(v)) { low[u]=min(low[u],low[v]); p=1; } } else if(father[u]!=i^1) { low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]&&p) { colorNum++; DFS(u); if(father[u]) { v=father[u]; imp[v]=shy[v]; v=father[u]^1;imp[v]=shy[v]; } } return p;}void Add2(int u,int v){ edges[e].v=v; edges[e].next=begin[u]; begin[u]=e++;}void Add3(int u,int v){ edges[e].v=v; edges[e].next=end[u]; end[u]=e++;}void Add4(int u,int v){ edges[e].v=v; edges[e].next=query[u]; query[u]=e++;}void buildGraph(){ int i,j,v,x,y; for(i=2;i
                
                 rank[y]) swap(Qu[i],Qv[i]); Add4(color[Qu[i]],i); }}i64 dat(int a){ int u=edges[a^1].v; int v=edges[a].v; return disS[u]+edges[a].dis+disT[v];}int cmp(int a,int b){ return dat(a)>dat(b);}void solve(){ clr(visit,0); int i,j,k,p=0,v; for(i=color[S];i;i=go[i]) { for(j=end[i];j!=-1;j=edges[j].next) { v=edges[j].v; visit[v]=1; } for(j=begin[i];j!=-1;j=edges[j].next) { v=edges[j].v; if(!imp[v]) f[++p]=v,push_heap(f+1,f+p+1,cmp); else k=v; } while(p&&visit[f[1]]) pop_heap(f+1,f+p+1,cmp),p--; for(j=query[i];j!=-1;j=edges[j].next) { v=edges[j].v; if(Qu[v]==edges[k^1].v&&Qv[v]==edges[k].v) { ans[v]=p?dat(f[1]):-1; } else { ans[v]=disS[T]; } } }}int main(){ while(scanf("%d%d",&n,&m)!=-1) { init(); int i,u,v,d; for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&d); Add1(u,v,d); Add1(v,u,d); } scanf("%d%d%d",&S,&T,&m); Dij(S,disS); Dij(T,disT); BFS(S); Tarjan(S); buildGraph(); solve(); for(i=1;i<=m;i++) { if(ans[i]==-1) puts("Infinity"); else printf("%lld\n",ans[i]); } } return 0;}