题意

分析

我们可以先把原图的一条最短路找出来。假设询问一条不在最短路上的边，则答案就为最短路。现在考虑如果删掉一条最短路上的边(x,y)后的答案。 显然答案一定是s-s’-x-y-t’-t其中s’和t’是在最短路上的点，而x,y则不是。 对于每一个点x，求出fs[x]表示从s到x的最短路上，一定是s-s’-x的形式，其中的s’是多少。ft[x]表示从x到t的路径上的t’是多少。 那么对于原图中的每一条边(x,y)，如果强制选择这条边的话，就可以对最短路上(fs[x],ft[y])这条路径上的边的答案做出贡献。只要用线段树维护一下即可。

然而我并不会证明这个算法的正确性，而且据网上有人说这个做法是有反例的。。。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long LL; const int N=200005; const LL inf=(LL)1e15; int n,m,cnt,last[N],fs[N],ft[N],s,t,id[N]; LL dis[N],ds[N],dt[N]; struct edge{int to,next;LL w;bool use;}e[N*2]; priority_queue<pair<LL,int> > heap; bool vis[N]; int read() { int 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; } void addedge(int u,int v,int w) { e[++cnt].to=v;e[cnt].w=w;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].w=w;e[cnt].next=last[v];last[v]=cnt; } void dij() { for (int i=1;i<=n;i++) dis[i]=inf,vis[i]=0; dis[s]=0;heap.push(make_pair(0,s)); for (int i=1;i<=n;i++) { while (!heap.empty()&&vis[heap.top().second]) heap.pop(); if (heap.empty()) break; int x=heap.top().second;heap.pop();vis[x]=1; for (int i=last[x];i;i=e[i].next) if (dis[x]+e[i].w<dis[e[i].to]) { dis[e[i].to]=dis[x]+e[i].w; heap.push(make_pair(-dis[e[i].to],e[i].to)); } } int now=1,x=t;id[t]=now; while (x!=s) { for (int i=last[x];i;i=e[i].next) if (dis[e[i].to]+e[i].w==dis[x]) { x=e[i].to;e[i].use=e[i^1].use=1;break; } id[x]=++now; } } void prework() { for (int i=1;i<=n;i++) ds[i]=inf,vis[i]=0; ds[s]=0;heap.push(make_pair(0,s));fs[s]=id[s]; for (int i=1;i<=n;i++) { while (!heap.empty()&&vis[heap.top().second]) heap.pop(); if (heap.empty()) break; int x=heap.top().second;heap.pop();vis[x]=1; for (int i=last[x];i;i=e[i].next) if (ds[x]+e[i].w<ds[e[i].to]) { ds[e[i].to]=ds[x]+e[i].w; if (id[e[i].to]) fs[e[i].to]=id[e[i].to]; else fs[e[i].to]=fs[x]; heap.push(make_pair(-ds[e[i].to],e[i].to)); } } for (int i=1;i<=n;i++) dt[i]=inf,vis[i]=0; dt[t]=0;heap.push(make_pair(0,t));ft[t]=id[t]; for (int i=1;i<=n;i++) { while (!heap.empty()&&vis[heap.top().second]) heap.pop(); if (heap.empty()) break; int x=heap.top().second;heap.pop();vis[x]=1; for (int i=last[x];i;i=e[i].next) if (dt[x]+e[i].w<dt[e[i].to]) { dt[e[i].to]=dt[x]+e[i].w; if (id[e[i].to]) ft[e[i].to]=id[e[i].to]; else ft[e[i].to]=ft[x]; heap.push(make_pair(-dt[e[i].to],e[i].to)); } } } struct Sig_tree { struct tree{LL mn;}t[N*5]; void ins(int d,int l,int r,int x,int y,LL z) { if (x>y) return; if (l==x&&r==y) { t[d].mn=min(t[d].mn,z); return; } int mid=(l+r)/2; ins(d*2,l,mid,x,min(y,mid),z); ins(d*2+1,mid+1,r,max(x,mid+1),y,z); } LL query(int d,int l,int r,int x) { if (l==r) return t[d].mn; int mid=(l+r)/2; if (x<=mid) return min(query(d*2,l,mid,x),t[d].mn); else return min(query(d*2+1,mid+1,r,x),t[d].mn); } }Sig; int main() { n=read();m=read();cnt=1; for (int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); addedge(x,y,z); } s=read();t=read(); dij(); prework(); for (int i=1;i<=n*4;i++) Sig.t[i].mn=inf; for (int i=2;i<=cnt;i+=2) { if (e[i].use) continue; int x=e[i].to,y=e[i+1].to; int p=fs[x],q=ft[y]; if (p>q) Sig.ins(1,1,n,q,p-1,ds[x]+e[i].w+dt[y]); p=fs[y];q=ft[x]; if (p>q) Sig.ins(1,1,n,q,p-1,ds[y]+e[i].w+dt[x]); } int q=read(); while (q--) { int x=read(),y=read(); if (abs(id[x]-id[y])!=1||!id[x]||!id[y]) printf("%lld\n",dis[t]); else { LL ans=Sig.query(1,1,n,min(id[x],id[y])); if (ans==inf) puts("Infinity"); else printf("%lld\n",ans); } } return 0; }