http://poj.org/problem?id=3463
要 深入了解 dij 的标号技术，一但 被标记 ，怎不会 被第二次 标记 。//注意 是有向图。。。。
/* 2 求s到t的最短路与次短路（这里要求只比最短路多1）的条数之和
3
4 联想到最小，次小的一种更新关系：
5 if(x<最小)更新最小，次小
6 else if(==最小)更新方法数
7 else if(x<次小)更新次小
8 else if(x==次小)更新方法数
9
10 同时记录s到u最短，次短路及方法数
11
12 还是那个原理，第一次遇到的就是最优的，然后vi标记为真
13 方法数注意是加法原理，不是乘法
14 \
15 -- u -- v 所以是加法原理 16 */
dis[i][0] 表示 最短距离 dis[i][1]表示 原点 到 i 的 次短距离
cnt[i][0] 表示 最短录得 条数 ， cnt[i][1]同上。
我i们 只需要 不断的 运用 优先队列 不断更新 就可 了
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 10000000
16
17 //freopen("data.txt","r",stdin);
18 const double pi = acos(-1.0);
19 typedef __int64 ll;
20 const int maxn = 1200 ;
21 using namespace std;
22 struct enode
23 {
24 int to;
25 int len ;
26 int next ;
27 }p[maxn*10] ;
28 int num,n,m ,dis[maxn][2],cnt[maxn][2],vis[maxn][2],next[maxn];
29 struct node
30 {
31 int x;
32 int ty;
33 node(int a,int b):x(a),ty(b){}
34
35 friend bool operator < (node a,node b)
36 {
37 return dis[a.x][a.ty] > dis[b.x][b.ty] ;
38 }
39 };
40
41 void add(int from,int to ,int len )
42 {
43 p[num].to = to;
44 p[num].len = len ;
45 p[num].next = next[from];
46 next[from] = num ++ ;
47 }
48 void init()
49 {
50 num = 0 ;
51 CL(next,-1) ;
52 }
53 priority_queue<node>que;
54 void dij(int s,int t )
55 {
56 int i,j ;
57 while(!que.empty())que.pop() ;
58 for(i = 0 ; i <= n;i++)
59 {
60 for(j = 0 ; j < 2;j++)
61 {
62 dis[i][j] = inf ;
63 }
64 }
65 que.push(node(s,0));
66 CL(vis,0) ;
67 CL(cnt,0) ;
68 dis[s][0] = 0 ;
69 cnt[s][0] = 1 ;
70
71 while(!que.empty())
72 {
73
74 node a = que.top() ;que.pop() ;
75 int u = a.x ;
76 int f = a.ty ;
77
78 if(vis[u][f])continue ;// 防止 重复 计算
79
80 vis[u][f] = 1;//
81
82 for(i = next[u];i!= -1; i = p[i].next)
83 {
84 int to = p[i].to;
85 int len = p[i].len ;
86 int l = dis[u][f] + len ;
87 if(l < dis[to][0])// 不相等 则 更新
88 {
89 if(dis[to][0]!=inf)
90 {
91 dis[to][1] = dis[to][0];
92 cnt[to][1] = cnt[to][0] ;
93 que.push(node(to,1)) ;
94 }
95
96
97 dis[to][0] = l;
98 cnt[to][0] = cnt[u][f];
99
100 que.push(node(to,0));
101
102
103
104 }
105 else
106 if(l == dis[to][0]) cnt[to][0] += cnt[u][f] ; //相等
107 else if(l < dis[to][1])
108 {
109 dis[to][1] = l;
110 cnt[to][1] = cnt[u][f] ;
111
112
113 que.push(node(to,1));
114 }
115 else
116 {
117 if(l == dis[to][1]) cnt[to][1] += cnt[u][f] ;
118 }
119 }
120
121
122
123
124
125 }
126 }
127 int main()
128 {
129 //freopen("data.txt","r",stdin);
130 int i,j,x,y,len ,s,t;
131 int T ;
132 scanf("%d",&T);
133
134 while(T--)
135 {
136 scanf("%d%d",&n,&m) ;
137 init() ;
138 for(i = 0; i < m;i++)
139 {
140 scanf("%d%d%d",&x,&y,&len);
141 add(x,y,len);
142
143 }
144 scanf("%d%d",&s,&t) ;
145 dij(s,t);
146 if(dis[t][0] + 1 == dis[t][1] )
147 printf("%d\n",cnt[t][0] + cnt[t][1]) ;
148 else printf("%d\n",cnt[t][0]) ;
149 }
150 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 10000000
16
17 //freopen("data.txt","r",stdin);
18 const double pi = acos(-1.0);
19 typedef __int64 ll;
20 const int maxn = 1200 ;
21 using namespace std;
22 struct enode
23 {
24 int to;
25 int len ;
26 int next ;
27 }p[maxn*10] ;
28 int num,n,m ,dis[maxn][2],cnt[maxn][2],vis[maxn][2],next[maxn];
29 struct node
30 {
31 int x;
32 int ty;
33 node(int a,int b):x(a),ty(b){}
34
35 friend bool operator < (node a,node b)
36 {
37 return dis[a.x][a.ty] > dis[b.x][b.ty] ;
38 }
39 };
40
41 void add(int from,int to ,int len )
42 {
43 p[num].to = to;
44 p[num].len = len ;
45 p[num].next = next[from];
46 next[from] = num ++ ;
47 }
48 void init()
49 {
50 num = 0 ;
51 CL(next,-1) ;
52 }
53 priority_queue<node>que;
54 void dij(int s,int t )
55 {
56 int i,j ;
57 while(!que.empty())que.pop() ;
58 for(i = 0 ; i <= n;i++)
59 {
60 for(j = 0 ; j < 2;j++)
61 {
62 dis[i][j] = inf ;
63 }
64 }
65 que.push(node(s,0));
66 CL(vis,0) ;
67 CL(cnt,0) ;
68 dis[s][0] = 0 ;
69 cnt[s][0] = 1 ;
70
71 while(!que.empty())
72 {
73
74 node a = que.top() ;que.pop() ;
75 int u = a.x ;
76 int f = a.ty ;
77
78 if(vis[u][f])continue ;// 防止 重复 计算
79
80 vis[u][f] = 1;//
81
82 for(i = next[u];i!= -1; i = p[i].next)
83 {
84 int to = p[i].to;
85 int len = p[i].len ;
86 int l = dis[u][f] + len ;
87 if(l < dis[to][0])// 不相等 则 更新
88 {
89 if(dis[to][0]!=inf)
90 {
91 dis[to][1] = dis[to][0];
92 cnt[to][1] = cnt[to][0] ;
93 que.push(node(to,1)) ;
94 }
95
96
97 dis[to][0] = l;
98 cnt[to][0] = cnt[u][f];
99
100 que.push(node(to,0));
101
102
103
104 }
105 else
106 if(l == dis[to][0]) cnt[to][0] += cnt[u][f] ; //相等
107 else if(l < dis[to][1])
108 {
109 dis[to][1] = l;
110 cnt[to][1] = cnt[u][f] ;
111
112
113 que.push(node(to,1));
114 }
115 else
116 {
117 if(l == dis[to][1]) cnt[to][1] += cnt[u][f] ;
118 }
119 }
120
121
122
123
124
125 }
126 }
127 int main()
128 {
129 //freopen("data.txt","r",stdin);
130 int i,j,x,y,len ,s,t;
131 int T ;
132 scanf("%d",&T);
133
134 while(T--)
135 {
136 scanf("%d%d",&n,&m) ;
137 init() ;
138 for(i = 0; i < m;i++)
139 {
140 scanf("%d%d%d",&x,&y,&len);
141 add(x,y,len);
142
143 }
144 scanf("%d%d",&s,&t) ;
145 dij(s,t);
146 if(dis[t][0] + 1 == dis[t][1] )
147 printf("%d\n",cnt[t][0] + cnt[t][1]) ;
148 else printf("%d\n",cnt[t][0]) ;
149 }
150 }