1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<queue> 5 #define VM 1005 6 #define EM 10010 7 using namespace std; 8 const int inf=0x3f3f3f3f; 9 int head[VM],cnt[VM][2],dist[VM][2],vis[VM][2];//dis[i][0]为最短路，dis[i][1]为次短路10 int e,src,des,n,m;11 struct E12 {13     int to,w,next;14 } edge[EM];15 void add(int cu,int cv,int cw)16 {17     edge[e].to=cv;18     edge[e].w=cw;19     edge[e].next=head[cu];20     head[cu]=e ++;21 }22 int dij()23 {24     int i,j,u,min,flag;25     memset(dist,0x3f,sizeof(dist));26     memset(vis,0,sizeof(vis));27     memset(cnt,0,sizeof(cnt));28     dist[src][0]=0;29     cnt[src][0]=1;30     for(i=1;i<2*n;i++)31     {32         min=inf;33         for(j=1;j<=n;j++)           //找新的最短路和次短路34             if(!vis[j][0]&&dist[j][0]<min)35             {36                 u=j;37                 flag=0;38                 min=dist[j][0];39             }40             else if(!vis[j][1]&&dist[j][1]<min)41             {42                 u=j;43                 flag=1;44                 min=dist[j][1];45             }46         if(min==inf)47             break;48         vis[u][flag]=1;49         for(j=head[u];j!=-1;j=edge[j].next)50         {51             int v=edge[j].to;52             int w=edge[j].w+min;53             if(dist[v][0]>w) //如果找到的新的值比最短路小，则更新最短路和次短路的值54             {55                 dist[v][1]=dist[v][0];//更新次短路56                 dist[v][0]=w;// 更新最短路57                 cnt[v][1]=cnt[v][0];58                 cnt[v][0]=cnt[u][flag];//更新最短路和次短路的个数59 60             }61             else if(dist[v][0]==w)   //如果值等于最短路62                 cnt[v][0]+=cnt[u][flag];//更新最短路的个数63             else if(dist[v][1]>w)    //如果找到的值小于次短路的值，更新次短路64             {65                 dist[v][1]=w;    //更新次短路的值66                 cnt[v][1]=cnt[u][flag];  //更新次短路的个数67             }68             else if(dist[v][1]==w)   //如果找到的值等于次短路的值69                 cnt[v][1]+=cnt[u][flag];//更新次短路的个数70         }71 72     }73     if(dist[des][0]+1==dist[des][1])//如果次短路的值等于最短路值+174         cnt[des][0]+=cnt[des][1];75     return cnt[des][0];76 }77 int main()78 {79     int T,u,v,w;80     scanf("%d",&T);81     while(T--)82     {83         scanf("%d%d",&n,&m);84         memset(head,0xff,sizeof(head));85         e=0;86         while(m--)87         {88             scanf("%d%d%d",&u,&v,&w);89             add(u,v,w);90         }91         scanf("%d%d",&src,&des);92         int ans=dij();93         printf("%d\n",ans);94     }95     return 0;96 }