1 /*   2  *题目大意：   3  *在一个有向图中,求从s到t两个点之间的最短路和比最短路长1的次短路的条数之和;   4  *   5  *算法思想：   6  *用A*求第K短路,目测会超时,直接在dijkstra算法上求次短路;   7  *将dist数组开成二维的,即dist[v][2],第二维分别用于记录最短路和次短路;   8  *再用一个cnt二维数组分别记录最短路和次短路的条数;   9  *每次更新路径的条数时,不能直接加1,,应该加上cnt[u][k],k为次短路径或者最短路径的标记;  10  *图有重边,不能用邻接矩阵存储;  11  *不知道为什么,题目上说的是N and M, separated by a single space, with 2≤N≤1000 and 1 ≤ M ≤ 10000;  12  *而我的代码硬是把N开成1W了才过,求解释,RE了无数次,擦;  13 **/  14 #include<iostream>   15 #include<cstdio>   16 #include<cstring>   17 #include<string>   18 #include<algorithm>   19 using namespace std;   20     21 const int N=11111;   22 const int M=111111;   23 const int INF=0xffffff;   24     25 struct node   26 {   27     int to;   28     int w;   29     int next;   30 };   31     32 node edge[N];   33 int head[N];   34     35 int dist[N][2],cnt[N][2];   36 bool vis[N][2];   37 int n,m,s,t,edges;   38     39 void addedge(int u,int v,int w)   40 {   41     edge[edges].w=w;   42     edge[edges].to=v;   43     edge[edges].next=head[u];   44     head[u]=edges++;   45 }   46     47 int dijkstra()   48 {   49     int k;   50     for(int i=0; i<=n; i++)   51     {   52         dist[i][0]=dist[i][1]=INF;   53         vis[i][0]=vis[i][1]=0;   54         cnt[i][0]=cnt[i][1]=0;   55     }   56     cnt[s][0]=1,dist[s][0]=0;   57     58     for(int i=1; i<=n*2; i++)   59     {   60         int u=-1;   61         int min_dist=INF;   62         for(int j=1; j<=n; j++)   63             for(int flag=0; flag<2; flag++)   64                 if(!vis[j][flag]&&dist[j][flag]<min_dist)   65                 {   66                     min_dist=dist[j][flag];   67                     u=j;   68                     k=flag;   69                 }   70         if(u==-1)   71             break;   72         vis[u][k]=true;   73         for(int e=head[u]; e!=-1; e=edge[e].next)   74         {   75             int j=edge[e].to;   76             int tmp=dist[u][k]+edge[e].w;   77     78             if(tmp<dist[j][0])//tmp小于最短路径长:   79             {   80                 dist[j][1]=dist[j][0];//次短路径长   81                 cnt[j][1]=cnt[j][0];//次短路径计数   82                 dist[j][0]=tmp;//最短路径长   83                 cnt[j][0]=cnt[u][k];//最短路径计数   84             }   85     86             else if(tmp==dist[j][0])//tmp等于最短路径长：   87             {   88                 cnt[j][0]+=cnt[u][k];//最短路径计数   89             }   90     91             else if(tmp<dist[j][1])//tmp大于最短路径长且小于次短路径长：   92             {   93                 dist[j][1]=tmp;//次短路径长   94                 cnt[j][1]=cnt[u][k];//次短路径计数   95             }   96     97             else if(tmp==dist[j][1])//tmp等于次短路径长：   98             {   99                 cnt[j][1]+=cnt[u][k];//次短路径计数  100             }  101         }  102     }  103    104     int res=cnt[t][0];  105     if(dist[t][0]+1==dist[t][1])//判断最短路和次短路是否相差1  106         res+=cnt[t][1];  107     return res;  108 }  109    110 int main()  111 {  112     //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);  113     int tcase;  114     scanf("%d",&tcase);  115     while(tcase--)  116     {  117         edges=0;  118         scanf("%d%d",&n,&m);  119         memset(head,-1,sizeof(head));  120         int u,v,w;  121         for(int i=0; i<m; i++)  122         {  123             scanf("%d%d%d",&u,&v,&w);  124             addedge(u,v,w);  125         }  126         scanf("%d%d",&s,&t);  127         printf("%d\n",dijkstra());  128     }  129     return 0;  130 }