問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1511思路:
第一次寫SPFA，其實是在discuss里總是看到SPFA這東東，于是今天就好奇地查了下，原來是求最短路徑的快速算法
除了SPFA，這題還學到了:
1. 如何靜態地建立鄰接表，大開眼界，原來鄰接表還可以這么建的，膜拜...
2. 求一個頂點到其他各個頂點的最短路徑，顯然，是單源最短路徑
求其他各個頂點到某一個特定頂點的最短路徑，其實也是單源最短路徑，只要將原始有向圖逆向即可
參考:
http://www.cnblogs.com/zhangjinglei/archive/0001/01/01/1532389.html代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 1000005
5 #define INF 0x7FFFFFFF
6 struct Edge { /* build adj-list statically */
7 int to;
8 int cost;
9 int next;
10 };
11 struct Edge edges[MAX_N], op_edges[MAX_N];
12 int assist[MAX_N], op_assist[MAX_N];
13 int mark[MAX_N], d[MAX_N];
14 int queue[MAX_N];
15 int P, Q;
16
17 void
18 init()
19 {
20 int i, f, t, c;
21 scanf("%d %d", &P, &Q);
22 memset(assist, -1, sizeof(assist));
23 memset(op_assist, -1, sizeof(op_assist));
24 for(i=0; i<Q; i++) {
25 scanf("%d %d %d", &f, &t, &c);
26 edges[i].to = t;
27 edges[i].cost = c;
28 edges[i].next = assist[f];
29 assist[f] = i;
30 /* reverse graph */
31 op_edges[i].to = f;
32 op_edges[i].cost = c;
33 op_edges[i].next = op_assist[t];
34 op_assist[t] = i;
35 }
36 }
37
38 long long
39 spfa(struct Edge *e, int *ass, int begin)
40 {
41 int i, j, head, tail, cur;
42 memset(mark, 0, sizeof(mark));
43 for(i=1; i<=P; i++)
44 d[i] = INF;
45 head = -1;
46 tail = 0;
47 d[begin] = 0;
48 mark[begin] = 1;
49 queue[tail] = begin;
50 while(head < tail) {
51 ++head;
52 cur = queue[head];
53 mark[cur] = 0;
54 for(j=ass[cur]; j!=-1; j=e[j].next) {
55 if(d[e[j].to] > d[cur]+e[j].cost) {
56 d[e[j].to] = d[cur] + e[j].cost;
57 if(!mark[e[j].to]) {
58 ++tail;
59 queue[tail] = e[j].to;
60 mark[e[j].to] = 1;
61 }
62 }
63 }
64 }
65 long long rt = 0;
66 for(i=1; i<=P; i++)
67 rt += d[i];
68 return rt;
69 }
70
71 int
72 main(int argc, char **argv)
73 {
74 int tests;
75 scanf("%d", &tests);
76 while(tests--) {
77 init();
78 printf("%lld\n", spfa(edges, assist, 1)+spfa(op_edges, op_assist, 1));
79 }
80 }