题目链接：http://poj.org/problem?id=3463
题意：求最短路和比最短路大1的路条数。
思路：这里只要把dijkstra变形就可以了。一般的dijkstra只是求最短路。而这里求出最短路和次短路 和他们的条数。
思路是一样的，找到一条没访问的最小边，再通过它更新最短距离。
这里也是，只不这里要找2*n-1次 没访问过的最小边 ，因为要找到出起点外 n-1个点最短路 和所以n个点的次短路。
再更新，这里的更新条件就不只是一个情况了。有四种：（假设 minx是目前找到的最小边，v是需要更新的点，w是到更新点v的边权 ）
d[v][0]存最短路值,d[v][1]存次短路值
1. d[v][0]>minx+w 更新最短距离（但是记得更新次短距离，次短距离一定大于d[v][0]，当d[v][0]更新成minx+w时，次短距离更新成原来的d[v][0]）
2.d[v][0]==minx+w 找到相同最短距离，更新最短条数
3.d[v][1]>minx+w 更新次短距离
3.d[v][1]==minx+w 找到相同次短距离，更新次短条数
详情看代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=1100; const int maxm=10100; struct node{ int u,v,w,nxt; }e[maxm]; int d[maxn][2],ans[maxn][2],vis[maxn][2],head[maxn]; int n,m,st,ed,cnt; //d[][0]最短距离，d[][1]次短距离,ans[][]最短，次短条数 void add(int u,int v,int w) { e[cnt]={u,v,w,head[u]}; head[u]=cnt++; } int dij() { memset(d,0x3f,sizeof(d)); memset(vis,0,sizeof(vis)); memset(ans,0,sizeof(ans)); ans[st][0]=1; d[st][0]=0; for(int i=1;i<2*n;i++) { int minx=inf,u,flag; for(int j=1;j<=n;j++) { if(!vis[j][0]&&minx>d[j][0]) { minx=d[j][0]; u=j; flag=0; } else if(!vis[j][1]&&minx>d[j][1]) { minx=d[j][1]; u=j; flag=1; } } //cout<<u<<endl; if(minx==inf) break; vis[u][flag]=1; for(int j=head[u];j!=-1;j=e[j].nxt) { int v=e[j].v; int w=e[j].w; if(d[v][0]>minx+w)//1 { ans[v][1]=ans[v][0]; d[v][1]=d[v][0]; d[v][0]=minx+w; ans[v][0]=ans[u][flag]; } else if(d[v][0]==minx+w)//2 ans[v][0]+=ans[u][flag]; else if(d[v][1]>minx+w)//3 { d[v][1]=minx+w; ans[v][1]=ans[u][flag]; } else if(d[v][1]==minx+w)//4 ans[v][1]+=ans[u][flag]; } } int res=ans[ed][0]; //cout<<d[ed][0]<<' '<<d[ed][1]<<endl; if(d[ed][1]==d[ed][0]+1) res+=ans[ed][1]; printf("%d ",res); } int main() { int t,u,v,w; scanf("%d",&t); while(t--) { cnt=0; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); } scanf("%d%d",&st,&ed); dij(); } return 0; }