DP真的是相當(dāng)相當(dāng)?shù)貜姶蟀?..
dp[i][1]表示到達點i最短的路有多少條，dp[i][2]表示次短的條數(shù)
dist[i][1]表示到達點i最短路的長度,dist[i][2].........................
初始化為dist[st][1]=0 其他為max_int dp[st][1]=1 其他為0
用v去松馳u時有四種情況 (設(shè)當(dāng)前dist[v][cas])
情況1：dist[v][cas]+w(v,u)<dist[u][1]，找到一個更短的距離，則把原來最短的距離作為次短的距離，同時更新最短的.即
dist[u][2]=dist[u][1]
dist[u][1]=dist[v][cas]+w(v,u);
dp[u][2]=dp[u][1]
dp[u][1]=dp[v][cas]，
把Node(dist[u][1],u,1)和Node(dist[u][2],u,2)放入隊列
情況2：dist[v][cas]+w(v,u)==dist[u][1]，找到一條新的相同距離的最短路，則dp[u][1]+=dp[v][cas],其他不用更新,也不入隊
情況3：dist[v][cas]+w(v,u)<dist[u][2]，不可以更新最短距離，但可以更新次短的，則更新dist[u][2]和dp[u][2]
dist[u][2]=dist[v][cas]+w(v,u);
dp[u][2]=dp[v][cas];
把Node(dist[u][2],u,2)放入隊列
情況4：dist[v][cas]+w(v,u)==dist[u][2] 找到一條新的相同距離的次短路,則dp[u][2]+=dp[v][cas],其他不更新。
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 1001
5 #define INF 0x7FFFFFFF
6 int d[MAX_N][2], in[MAX_N][2], cnt[MAX_N][2];
7 int n, m, from, to;
8 struct Node {
9 int target, cost;
10 struct Node *next;
11 };
12 struct Node *nodes[MAX_N]; /* adj list: there may be different roads between city A and city B */
13
14 void
15 init()
16 {
17 int i, f, t, c;
18 struct Node *fresh;
19 memset(nodes, 0, sizeof(nodes));
20 scanf("%d %d", &n, &m);
21 for(i=0; i<m; i++) {
22 scanf("%d %d %d", &f, &t, &c);
23 fresh = (struct Node *)malloc(sizeof(struct Node));
24 fresh->target = t;
25 fresh->cost = c;
26 fresh->next = nodes[f];
27 nodes[f] = fresh;
28 }
29 scanf("%d %d", &from, &to);
30 }
31
32 void
33 dijkstra()
34 {
35 int i, j, k, p, min, v, cur;
36 struct Node *tmp;
37 memset(in, 0, sizeof(in));
38 memset(cnt, 0, sizeof(cnt));
39 /* d[i][0]: minimum path, d[i][1]: second minimum path */
40 for(i=1; i<=n; i++)
41 d[i][0] = d[i][1] = INF;
42 d[from][0] = 0;
43 cnt[from][0] = 1;
44 for(i=1; i<=2*n; i++) { /* each vertex has two chance to relax */
45 min = INF;
46 p = -1;
47 for(j=1; j<=n; j++) {
48 if(!in[j][0] && d[j][0]<min) {
49 min = d[j][0];
50 p = j;
51 k = 0;
52 } else if(!in[j][1] && d[j][1]<min) {
53 min = d[j][1];
54 p = j;
55 k = 1;
56 }
57 }
58 if(p == -1)
59 break;
60 in[p][k] = 1;
61 tmp = nodes[p];
62 while(tmp != NULL) { /* Relax */
63 v = tmp->target;
64 cur = d[p][k] + tmp->cost;
65 if(cur < d[v][0]) {
66 d[v][1] = d[v][0];
67 cnt[v][1] = cnt[v][0];
68 d[v][0] = cur;
69 cnt[v][0] = cnt[p][k];
70 } else if(cur == d[v][0]) {
71 cnt[v][0] += cnt[p][k];
72 } else if(cur < d[v][1]) {
73 d[v][1] = cur;
74 cnt[v][1] = cnt[p][k];
75 } else if(cur == d[v][1]) {
76 cnt[v][1] += cnt[p][k];
77 }
78 tmp = tmp->next;
79 }
80 }
81 }
82
83 int
84 main(int argc, char **argv)
85 {
86 int tests, rt;
87 scanf("%d", &tests);
88 while(tests--) {
89 init();
90 dijkstra();
91 rt = cnt[to][0];
92 if(d[to][0]+1 == d[to][1])
93 rt += cnt[to][1];
94 printf("%d\n", rt);
95 }
96 }