题意：求两点之间最短路的数目加上比最短路长度大1的路径数目
分析：可以转化为求最短路和次短路的问题，如果次短路比最短路大1，那么结果就是最短路数目加上次短路数目，否则就不加。
求解次短路的过程也是基于Dijkstra的思想。算法中用一个二维数组d[u][tag]（tag=0代表最短路，1代表次短路）来记录最短路和次短路的长度，cnt[u][tag]记录二者的数目。所以每个点都有两个访问状态，一个是最短路已经确定，另一个是次短路已经确定，所以vis[u][tag]数组也是二维的。
每次维护邻接点的状态时，有四种可能情况：
1.最短路长度需要更新。此时还需判断次短路是否需要更新，若最短路不存在，则不用更新；若最短路存在，则用最短路覆盖次短路。
2.最短路数目需要更新。传递过来的路径长度与当前最短路相等，那么数量要加上去。
3.次短路长度需要更新。
4.次短路数目需要更新。
且算法可以用优先队列改善效率。
#include<iostream> #include<stdio.h> #include<cstring> #include<queue> #include<cmath> #include<algorithm> #include<vector> using namespace std; typedef int LL; const int maxn =1e3+5,maxm = 2e4+5; const LL INF =0x3f3f3f3f; LL dis[maxn][2]; //最短路和次短路长度 struct Edge{ int to,next; LL val; }; struct Node{ int u,tag; bool operator <(const Node &rhs) const {return dis[u][tag]>dis[rhs.u][rhs.tag];} }; struct SPFA{ int n,m,tot; Edge edges[maxm]; int head[maxn]; bool vis[maxn][2]; int cnt[maxn][2]; //最短路和次短路条数 void init(int n){ this->n = n; this->tot=0; memset(head,-1,sizeof(head)); } void Addedge(int u,int v ,LL dist){ edges[tot].to = v; edges[tot].val = dist; edges[tot].next = head[u]; head[u] = tot++; } void spfa(int s){ for(int i=0;i<=n;++i){ dis[i][0]=INF,cnt[i][0]=0; dis[i][1]=INF,cnt[i][1]=0; vis[i][0]=vis[i][1]=false; } dis[s][0]=0,cnt[s][0]=1; priority_queue<Node> Q; Q.push((Node){s,0}); while(!Q.empty()){ Node x =Q.top();Q.pop(); int u = x.u,tag = x.tag; if(vis[u][tag]) continue; vis[u][tag] = true; for(int i=head[u];~i;i=edges[i].next){ int v =edges[i].to,w =edges[i].val; int tmp = dis[u][tag] + w; if(dis[v][0]>tmp) { //需要更新最短路 if(dis[v][0]!=INF){ //将次短路覆盖 dis[v][1] = dis[v][0]; cnt[v][1] = cnt[v][0]; Q.push((Node){v,1}); } dis[v][0]=tmp; cnt[v][0]=cnt[u][tag]; Q.push((Node){v,0}); } else if(dis[v][0]==tmp){ //最短路长度不变，数量增加 cnt[v][0]+=cnt[u][tag]; } else if(dis[v][1]>tmp){ //次短路长度改变 dis[v][1] = tmp; cnt[v][1] = cnt[u][tag]; Q.push((Node){v,1}); } else if(dis[v][1]==tmp){ //次短路长度不变，数量增加 cnt[v][1]+=cnt[u][tag]; } } } } }G; #define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int T,N,M,u,v, s,t; LL tmp; scanf("%d",&T); while(T--){ scanf("%d%d",&N,&M); G.init(N); for(int i=1;i<=M;++i){ scanf("%d%d%d",&u,&v,&tmp); G.Addedge(u,v,tmp); } scanf("%d%d",&s,&t); G.spfa(s); if(dis[t][1]==dis[t][0]+1) G.cnt[t][0]+=G.cnt[t][1]; printf("%d ",G.cnt[t][0]); } return 0; }