题目链接：点击打开链接
题目大意：略。
解题思路：注意：因为一开始 mi==0 导致 0+无法到达的点（INF）==INF==dist[i]，s.t. count[i] 误被更新，所以结束判断时，如果没有到达的点 i，需要 count[i]=0。
AC 代码
voidShortestDist( MGraphGraph, intdist[], intcount[], VertexS ) { intvis[MaxVertexNum]; for(inti=0;i<MaxVertexNum;i++) dist[i]=INFINITY, vis[i]=count[i]=0; dist[S]=0, count[S]=1; while(1) { intmi=INFINITY; S=-1; for(inti=0;i<Graph->Nv;i++) if(!vis[i] &&mi>dist[i]) mi=dist[i], S=i; if(S==-1) break; vis[S]=1; for(inti=0;i<Graph->Nv;i++) { if(!vis[i] &&mi+Graph->G[S][i]<dist[i]) dist[i]=mi+Graph->G[S][i], count[i]=count[S]; elseif(!vis[i] &&mi+Graph->G[S][i]==dist[i]) // 注释针对点count[i]+=count[S]; } } for(inti=0;i<MaxVertexNum;i++) if(dist[i]==INFINITY) dist[i]=-1, count[i]=0; }
