求出最短路径树，对于一个询问(x,y) 若不在树上S->T的链上，则答案不变，若在链上，考虑用一条非树边替换这条边，这条非树边必须跨越x->y这条边，线段树维护区间最小值

#include
     
      #include
      
       #include
       
        #include
        
         #define pr pair
         
          #define mp make_pair#define sc secondusing namespace std;int cnt,n,m,last[200005],Lv[200005],stack[200005],Fa[200005],vis[200005],pre[200005],Vis[1000005];long long dis[200005][2],Dep[200005],ANS[200005],tree[800005];priority_queue
          
           
            ,greater
            
              > q;struct node{ int to,next; long long val;}e[400005];struct node1{ int x,y,val;}E[200005];void add(int a,int b,int c){ e[++cnt].to=b; e[cnt].next=last[a]; e[cnt].val=c; last[a]=cnt;}void Dijkstra(int S,int cas){ for (int i=1; i<=n; i++) dis[i][cas]=1ll<<60,vis[i]=0; dis[S][cas]=0; q.push(mp(0ll,S)); while (!q.empty()){ int x=q.top().sc; q.pop(); if (vis[x]) continue; vis[x]=1; for (int i=last[x]; i; i=e[i].next){ int V=e[i].to; if (dis[V][cas]>dis[x][cas]+e[i].val){ dis[V][cas]=dis[x][cas]+e[i].val; if (cas==0) pre[V]=x; q.push(mp(dis[V][cas],V)); } } }}void Pre(int x,int fa,long long dep){ Fa[x]=fa,Dep[x]=dep; for (int i=last[x]; i; i=e[i].next){ int V=e[i].to; if (V==fa) continue; Pre(V,x,dep+e[i].val); }}void solve(int x,int lv){ vis[x]=1; Lv[x]=lv; for (int i=last[x]; i; i=e[i].next){ int V=e[i].to; if (vis[V]) continue; solve(V,lv); }}bool cmp(node a,node b){ return a.to
             
              >1; if (x<=mid) insert(t<<1,l,mid,x,key); else insert(t<<1|1,mid+1,r,x,key); tree[t]=min(tree[t<<1],tree[t<<1|1]);}long long query(int t,int l,int r,int x,int y){ if (r
              
               y) return 1ll<<60; if (l>=x && r<=y) return tree[t]; int mid=(l+r)>>1; return min(query(t<<1,l,mid,x,y),query(t<<1|1,mid+1,r,x,y));}void build(int t,int l,int r){ if (l==r){ tree[t]=1ll<<60; return; } int mid=(l+r)>>1; build(t<<1,l,mid); build(t<<1|1,mid+1,r); tree[t]=max(tree[t<<1],tree[t<<1|1]);}int main(){ scanf("%d%d",&n,&m); for (int i=1; i<=m; i++){ scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].val); add(E[i].x,E[i].y,E[i].val); add(E[i].y,E[i].x,E[i].val); } int S,T; scanf("%d%d",&S,&T); Dijkstra(S,0); Dijkstra(T,1); cnt=0; memset(vis,0,sizeof(vis)); for (int i=1; i<=n; i++) last[i]=0; for (int i=1; i<=n; i++) if (pre[i]) { add(pre[i],i,dis[i][0]-dis[pre[i]][0]); add(i,pre[i],dis[i][0]-dis[pre[i]][0]); } Lv[S]=1; Pre(S,0,0); int now=T,top=0; while (now){ stack[++top]=now; vis[now]=1; Vis[now]=top; now=Fa[now]; } for (int i=1; i<=top/2; i++) swap(stack[i],stack[top-i+1]); for (int i=1; i<=top; i++) solve(stack[i],i); int cnt=0; for (int i=1; i<=m; i++){ int x=E[i].x,y=E[i].y; if (Vis[x] && Vis[y] && (Vis[y]==Vis[x]+1 || Vis[x]==Vis[y]+1)) continue; int X=Lv[x],Y=Lv[y]; if (X>Y) swap(X,Y),swap(x,y); e[++cnt]=(node){X,Y,dis[x][0]+dis[y][1]+E[i].val}; } sort(e+1,e+cnt+1,cmp); build(1,1,top); int Top=1; for (int i=1; i
               
                Y) swap(X,Y); if (ANS[X]!=1ll<<60) printf("%lld\n",ANS[X]); else printf("Infinity\n"); } } else { if (dis[T][0]!=1ll<<60) printf("%lld\n",dis[T][0]); else printf("Infinity\n"); } } return 0;}