这题和最短路计数差不多，只是多了个次短路判断，其实也是跟最短路一样是满足拓扑序的，也就是说不可能出队之后绕一个环回来次短路还变化了
因此也可以用迪杰斯特拉这种天然满足拓扑序的进行更新，只不过需要注意一下最短路和次短路的变化
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e4+10; int n,m; int h[N],ne[N],e[N],idx,w[N]; int dis[N][2]; int cnt[N][2]; int st[N][2]; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } struct node{ int d,type,id; bool operator > (const node &t) const{ return d>t.d; } }; void dij(int S){ memset(dis,0x3f,sizeof dis); memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); priority_queue<node,vector<node>,greater<node> > q; dis[S][0]=0; cnt[S][0]=1; q.push({0,0,S}); while(q.size()){ auto t=q.top(); q.pop(); int ver=t.id; int sign=t.type; if(st[ver][sign]) continue; st[ver][sign]=1; int i; for(i=h[ver];i!=-1;i=ne[i]){ int j=e[i]; if(dis[j][0]>dis[ver][sign]+w[i]){ dis[j][1]=dis[j][0],cnt[j][1]=cnt[j][0]; q.push({dis[j][1],1,j}); dis[j][0]=dis[ver][sign]+w[i]; cnt[j][0]=cnt[ver][sign]; q.push({dis[j][0],0,j}); } else if(dis[j][0]==dis[ver][sign]+w[i]){ cnt[j][0]+=cnt[ver][sign]; } else if(dis[j][1]>dis[ver][sign]+w[i]){ dis[j][1]=dis[ver][sign]+w[i]; cnt[j][1]=cnt[ver][sign]; q.push({dis[j][1],1,j}); } else if(dis[j][1]==dis[ver][sign]+w[i]){ cnt[j][1]+=cnt[ver][sign]; } } } } int main(){ int t; cin>>t; while(t--){ cin>>n>>m; int i; memset(h,-1,sizeof h); idx=0; for(i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; add(a,b,c); } int S,T; cin>>S>>T; dij(S); int ans=cnt[T][0]; if(dis[T][0]==dis[T][1]-1) ans+=cnt[T][1]; cout<<ans<<endl; } }