Sightseeing poj 求最短路数量和最短路长度加1的路的数量 经典题！
/*经典的dij统计路的数量的好题！增加一维表示最短和次短两个状态。0表示最短，1表示次短。邻接表和邻接阵结合使用。加快速度。在统计数量的部分有详细的注释。*/#include <stdio.h>#include <cstring>const int maxm=10001;const int maxn=1001;const int inf=1<<30;struct edge{ int from,to,next,w;}e[maxm];int head[maxn];int dist[maxn][2],cnt[maxn][2],vis[maxn][2];int t,n,m,top;void add(int i,int j,int w){ e[top].from=i; e[top].to=j; e[top].w=w; e[top].next=head[i]; head[i]=top++;}int main(){ int u,v,w,s,end; scanf("%d",&t); while(t--) { top=0; scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); memset(vis,false,sizeof(vis)); while(m--) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); } scanf("%d%d",&s,&end); memset(dist,0x7f,sizeof(dist)); memset(cnt,0,sizeof(cnt)); dist[s][0]=0; cnt[s][0]=1; for(int i=1;i<2*n;i++)//循环2n-1次，最短路n-1次，次短路n次 { int min=inf; int k,flag; for(int j=1;j<=n;j++) { if(!vis[j][0]&&dist[j][0]<min) min=dist[j][0],k=j,flag=0; if(!vis[j][1]&&dist[j][1]<min) min=dist[j][1],k=j,flag=1; } if(min==inf) break; vis[k][flag]=true; for(int j=head[k];j!=-1;j=e[j].next) { int u=e[j].to;//用邻接表遍历和k相连的所有节点，数据较大，这样速度较快 int val=min+e[j].w; if(dist[u][0]>val)//此条件为更新最短路 { dist[u][1]=dist[u][0];//此时原先的最短路dist[u][0]现在变为次短，将其赋值给dist[u][1]. cnt[u][1]=cnt[u][0]; dist[u][0]=val;//更新最短路的值 cnt[u][0]=cnt[k][flag];//直接更新最短路的数量 } else if(dist[u][0]==val)//如果当前路径长度和最短路径相同，则最短路径长度++ cnt[u][0]+=cnt[k][flag]; else if(dist[u][1]>val)//当前路径长度无法更新最短路，但是可以更新次短路。就进行更新。 { dist[u][1]=val; cnt[u][1]=cnt[k][flag]; } else if(dist[u][1]==val)//同上。 cnt[u][1]+=cnt[k][flag]; } } if(dist[end][1]-1==dist[end][0]) printf("%d\n",cnt[end][1]+cnt[end][0]); else printf("%d\n",cnt[end][0]); } return 0;}