本题和hdu3191是非常相似的，我们只需加一个判断条件dis[e][0]+1==dis[e][1]即可。要记得点的下标。
可以看看hdu3191http://www.cnblogs.com/BruceNoOne/p/3248474.html
#include <iostream> using namespace std; const int N=1009; const int inf=1<<30; int dis[N][2],step[N][2],head[N],vis[N][2]; struct node { int v,w,next; }map[N*N]; int n,s,e,tot; void add(int a,int b,int w) { map[tot].v=b; map[tot].w=w; map[tot].next=head[a]; head[a]=tot++; } void dij() { int i,flag; dis[s][0]=0; step[s][0]=1; while(1) { int min=inf; int u; for(i=1;i<=n;i++) { if(!vis[i][0]&&dis[i][0]<min) { u=i; min=dis[i][0]; flag=0; }else if(!vis[i][1]&&dis[i][1]<min) { min=dis[i][1]; u=i; flag=1; } } if(u==e&&flag==1)break; if(min==inf)break; vis[u][flag]=1; for(i=head[u];i+1;i=map[i].next) { int v=map[i].v; int w=dis[u][flag]+map[i].w; if(dis[v][0]>w) { if(dis[v][0]!=inf) { dis[v][1]=dis[v][0]; step[v][1]=step[v][0]; } dis[v][0]=w; step[v][0]=step[u][flag]; }else if(dis[v][0]==w) { step[v][0]+=step[u][flag]; }else if(dis[v][1]>w) { dis[v][1]=w; step[v][1]=step[u][flag]; }else if(dis[v][1]==w) { step[v][1]+=step[u][flag]; } } } } void init() { for(int i=0;i<=n;i++) { head[i]=-1; dis[i][1]=dis[i][0]=inf; step[i][1]=step[i][0]=0; vis[i][1]=vis[i][0]=0; } tot=0; } int main() { int m,a,b,i,w,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); for( i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&w); add(a,b,w); } scanf("%d%d",&s,&e); dij(); if(dis[e][1]==dis[e][0]+1) printf("%d ",step[e][0]+step[e][1]); else printf("%d ",step[e][0]); } return 0; }