我的参考题解：https://www.cnblogs.com/ccz181078/p/7907022.html；
不过我感觉题解的压位有问题，（1<<x）还不炸上天。不过这题数据水，好像怎么写都能对，这里放上我认为正确的写法
//正经解法是计算一个F(x)表示经过x的最短路条数，然后找F(A)+F(B)=F(T),用map来做。 //而且F(x)可能很大，还要取模，一个不够的话可能还要取两个。 //而网上的这种随机算法相比之下就显得很简洁了（但由于这题数据很弱好像这部分写错也可以过） //关于这种做法的正确性，显然所有的最短路都经过的点的f值为0 //那么为什么靠两个f值相同且非0且不能在树形图中互达的点能将图分成两个部分呢，我们可以考虑用一个点将两部分连起来 //这样这个点的f值为0，也就是说它能到所有点，那把它去掉图当然被分成两个部分。 #include<iostream> #include<cmath> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> using namespace std; typedef long long i64; typedef unsigned long long u64; typedef unsigned int u32; const int N=5e4+5; int n,m,pp,cp,fa[N],S,T,last[N],pre[N*2],other[N*2],w[N*2],t; void add(int x,int y,int z){ ++t;pre[t]=last[x];last[x]=t;other[t]=y;w[t]=z; } struct node{ int id; i64 dis; bool operator<(const node&a)const{ return dis>a.dis; } }A,B; priority_queue<node>q; bool vis[N]; i64 dis[N],ans=0; u64 f[N]; u32 can[N][N/32+5]; int _get(u32*a,int x){return (a[x>>5]>>(x&31))&1;} void _set(u32*a,int x){a[x>>5]|=1<<(x&31);} void _or(u32*a,u32*b){ int p=n/32+1; for(int i=0;i<=p;i+=4){ a[i]|=b[i];a[i+1]|=b[i+1]; a[i+2]|=b[i+2];a[i+3]|=b[i+3]; } } void f1(int x){//从T往回找最短路图，我觉得和从S开始找是一样的。 vis[x]=1; for(int i=last[x];i;i=pre[i]){ int v=other[i]; if(dis[v]+w[i]==dis[x]){ if(!vis[v])fa[v]=x,f1(v); else{ u64 z=rand(); z=z<<31^rand(); f[x]^=z;f[fa[v]]^=z; } } } } struct hehe{ int id; u64 v,dis; bool operator<(const hehe&a)const{ return v!=a.v?v<a.v:dis>a.dis; } }tmp[N]; void f2(int x){ _set(can[x],x); vis[x]=0; for(int i=last[x];i;i=pre[i]){ int v=other[i]; if(dis[v]+w[i]==dis[x]){ if(vis[v])f2(v),f[x]^=f[v]; _or(can[x],can[v]); } } if(f[x])tmp[pp++]=(hehe){x,f[x],dis[x]}; else ++cp; } void calc(){ f1(T);f2(T); sort(tmp,tmp+pp); for(int i=0,j=0;i<pp;i=j){ int t=1; for(++j;j<pp&&tmp[i].v==tmp[j].v;++j)t+=_get(can[tmp[i].id],tmp[j].id); //图一定可以分成两个部分，一部分是经过A的最短路，一部分是经过B的，两部分没有交集。 ans+=i64(j-i-t)*t;//因为f值相同的是按dis值排序的，所以此时的f一定是按A,B分的两个集合中的一个。 } ans+=cp*i64(n-cp-pp); printf("%lld ",ans); //system("pause"); } bool dijkstra(){ for(int i=0;i<=n;++i)dis[i]=1ll<<60; A.id=S;A.dis=0;dis[S]=0;q.push(A); while(!q.empty()){ B=q.top();q.pop(); if(B.dis!=dis[B.id])continue; if(B.id==T){calc();return 1;} for(int i=last[B.id];i;i=pre[i]){ int v=other[i]; if(dis[v]>dis[B.id]+w[i]){ dis[v]=dis[B.id]+w[i]; A.id=v;A.dis=dis[v];q.push(A); } } } return 0; } int main(){ int x,y,z; cin>>n>>m>>S>>T; srand(n^m^T^S^12341); for(int i=1;i<=m;++i){ scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } if(!dijkstra())printf("%lld ",n*i64(n-1)/2); //system("pause"); return 0; }