如果S==T，那么答案为0。

如果S与T不连通，那么答案为inf。

否则，S到T的最短路径上至少有一条边。

求出以S为源点的最短路图，是个DAG，随便抓一条S到T的最短路，记为P。

设dpS[x]表示在这个图上，能到达x点的离S最近的在P上的点，可以通过拓扑排序+DP求出。

然后求出以T为源点的最短路图，在T的最短路图里找到P。

设dpT[x]表示在这个图上，能到达x点的离T最近的在P上的点，同样可以通过拓扑排序+DP求出。

然后把P路径上的边按S到T的方向，从1开始标号。

对于一条边，如果不在P上，那么答案显然为S到T的最短路。

否则，对于一条不在P上的边长为w的有向边x->y，P中dpS[x]到dpT[y]-1之间的边删掉后，均可以用disS[x]+disT[y]+w代替。

用线段树维护即可，时间复杂度$O((n+m)\log n+q)$。

 

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;typedef pair
        
          P;const int N=200010;const ll inf=1LL<<60;int n,m,que,S,T,i,x,y,g[N],v[N<<1],w[N<<1],nxt[N<<1],ed;int G[N],V[N],NXT[N],pre[N],d[N];int path[N],cnt,id[N],fs[N],ft[N];int q[N],h,t;ll ds[N],dt[N];struct E{int x,y,z;}e[N];priority_queue
         
          
,greater
          
 >Q;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}inline void ADD(int x,int y){pre[y]=x;d[y]++;V[++ed]=y;NXT[ed]=G[x];G[x]=ed;}inline int onpath(int x,int y){ if(!id[x]||!id[y])return 0; if(id[x]+1==id[y])return id[x]; if(id[y]+1==id[x])return id[y]; return 0;}ll val[525000],ans[N];void build(int x,int a,int b){ val[x]=inf; if(a==b)return; int mid=(a+b)>>1; build(x<<1,a,mid),build(x<<1|1,mid+1,b);}void change(int x,int a,int b,int c,int d,ll p){ if(c<=a&&b<=d){val[x]=min(val[x],p);return;} int mid=(a+b)>>1; if(c<=mid)change(x<<1,a,mid,c,d,p); if(d>mid)change(x<<1|1,mid+1,b,c,d,p);}void dfs(int x,int a,int b){ if(a==b){ans[a]=val[x];return;} int mid=(a+b)>>1; val[x<<1]=min(val[x<<1],val[x]),dfs(x<<1,a,mid); val[x<<1|1]=min(val[x<<1|1],val[x]),dfs(x<<1|1,mid+1,b);}int main(){ read(n),read(m); for(i=1;i<=m;i++){ read(e[i].x),read(e[i].y),read(e[i].z); add(e[i].x,e[i].y,e[i].z); add(e[i].y,e[i].x,e[i].z); } read(S),read(T); if(S==T){ for(read(que);que--;puts("0")); return 0; } for(i=1;i<=n;i++)ds[i]=inf;Q.push(P(ds[S]=0,S)); while(!Q.empty()){ P t=Q.top();Q.pop(); if(ds[t.second]