求出最短路径树，对于一个询问(x,y) 若不在树上S->T的链上，则答案不变，若在链上，考虑用一条非树边替换这条边，这条非树边必须跨越x->y这条边，线段树维护区间最小值
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define pr pair<long long,int>
#define mp make_pair
#define sc second
using 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<pr,vector<pr>,greater<pr> > 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<b.to;
}
void insert(int t,int l,int r,int x,long long key){
if (l==r){
tree[t]=min(tree[t],key);
return;
}
int mid=(l+r)>>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<x || l>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<top; i++){
while (Top<=cnt && e[Top].to<=i){
insert(1,1,top,e[Top].next,e[Top].val);
Top++;
}
ANS[i]=query(1,1,top,i+1,top);
}
int q;
scanf("%d",&q);
int cc=0;
while (q--){
cc++;
int x,y;
scanf("%d%d",&x,&y);
if (Vis[x] && Vis[y] && (Vis[x]==Vis[y]+1 || Vis[y]==Vis[x]+1)){
if (dis[T][0]==1ll<<60) printf("Infinity
");
else{
int X=Lv[x],Y=Lv[y];
if (X>Y) swap(X,Y);
if (ANS[X]!=1ll<<60) printf("%lld
",ANS[X]);
else printf("Infinity
");
}
}
else {
if (dis[T][0]!=1ll<<60) printf("%lld
",dis[T][0]);
else printf("Infinity
");
}
}
return 0;
}