http://www.cnblogs.com/wally/archive/2013/04/16/3024490.html
http://blog.csdn.net/me4546/article/details/6584448
维护最短路长度d[i][0]和次短路d[i][1]，最短路条数dp[i][0]和次短路dp[i][1]
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 5010 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f struct Edge { int v,w; }; vector<Edge> g[55]; struct node { int v,dist; int mark;//标记，0为最短路，1为次短路； bool operator < (const node &p) const { if(p.dist != dist) return p.dist<dist; return p.v<v;//这儿如果不按顶点的大小排序，就wa了。 } }; int n,m,s,e; int dist[55][2]; int dp[55][2]; bool vis[55][2]; //dp[i][0]表示到达点i最短的路有多少条，dp[i][1]表示次短的条数 //dist[i][0]表示到达点i最短路的长度,dist[i][1]表示次短路的长度 /* 用v去松驰u时有四种情况 (设当前dist[v][cas]) 情况1：dist[v][cas]+w(v,u)<dist[u][0]，找到一个更短的距离，则把原来最短的距离作为次短的距离，同时更新最短的.即 dist[u][1]=dist[u][0] dist[u][0]=dist[v][cas]+w(v,u); dp[u][1]=dp[u][0] dp[u][0]=dp[v][cas]， 把node(dist[u][0],u,0)和node(dist[u][1],u,1)放入队列 情况2：dist[v][cas]+w(v,u)==dist[u][0]，找到一条新的相同距离的最短路，则dp[u][0]+=dp[v][cas],其他不用更新,也不入队 情况3：dist[v][cas]+w(v,u)<dist[u][1]，不可以更新最短距离，但可以更新次短的，则更新dist[u][1]和dp[u][1] dist[u][1]=dist[v][cas]+w(v,u); dp[u][1]=dp[v][cas]; 把node(dist[u][1],u,1)放入队列 情况4：dist[v][cas]+w(v,u)==dist[u][1] 找到一条新的相同距离的次短路,则dp[u][1]+=dp[v][cas],其他不更新。 */ void dijkstra(int start,int end) { for(int i=0;i<n;i++) { dist[i][0]=dist[i][1]=INF; } memset(dp,0,sizeof(dp)); memset(vis,false,sizeof(vis)); priority_queue<node> Q; node p,q; dist[start][0]=0; dp[start][0]=1; p.dist=0,p.mark=0,p.v=start; Q.push(p); while(!Q.empty()) { p=Q.top(); Q.pop(); if(vis[p.v][p.mark]) continue; //if(dist[p.v][p.mark]!=p.dist)continue; vis[p.v][p.mark]= true; for(int i=0;i<g[p.v].size();i++) { int v=g[p.v][i].v; int w=g[p.v][i].w; if(!vis[v][0] && p.dist+w <dist[v][0]) { //可能为次短路 if(dist[v][0]!=INF) { q.v=v,q.dist=dist[v][1],q.mark=1; dist[v][1]=dist[v][0]; dp[v][1]=dp[v][0]; Q.push(q); } dist[v][0]=p.dist+w; dp[v][0]=dp[p.v][p.mark]; q.v=v,q.dist=dist[v][0],q.mark=0; Q.push(q); } else if(!vis[v][0] && p.dist+w==dist[v][0]) { dp[v][0]+=dp[p.v][p.mark]; } else if(!vis[v][1] && p.dist+w<dist[v][1]) { dist[v][1]=p.dist+w; dp[v][1]=dp[p.v][p.mark]; q.dist=dist[v][1],q.v=v,q.mark=1; Q.push(q); } else if(!vis[v][1]&&p.dist+w==dist[v][1]) { dp[v][1]+=dp[p.v][p.mark]; } } } } int main(){ while(~scanf("%d%d%d%d",&n,&m,&s,&e)) { for(int i=0;i<n;i++)g[i].clear(); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); Edge p; p.v=v,p.w=w; g[u].push_back(p); } dijkstra(s,e); printf("%d %d ",dist[e][1],dp[e][1]); } return 0; }