隨筆檔案

2012年11月9日 明天就是NOIP 2012 Day1！

   再放一份代碼，其實我真的不會SPFA，集訓的時候，在國家集訓隊的論文里看到了一句話：“SPFA算法其實是Bellman-Ford算法的一個進一步優化的版本。”所以我把這個當成SPFA了，效果不錯，為了簡單起見用了STL。寫起來很像BFS的尋路，還很像DP的過程，所以很快就會理解。
   如果想用堆優化，就直接把隊列換成優先隊列就可以了。
   下面是代碼：
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 
 6 #define MAXN 10007
 7 #define INF 100000007
 8 
 9 typedef struct G_NODE
10 {
11     int u, v, w;
12     struct G_NODE *next;
13 } Gnode;
14 
15 int n, m, d[MAXN];
16 Gnode *a[MAXN];
17 
18 void add_edge(int x, int y, int w)
19 {
20     Gnode *p = new Gnode;
21     p->u = x;
22     p->v = y;
23     p->w = w;
24     p->next = a[x]->next;
25     a[x]->next = p;
26 }
27 
28 bool bellman_ford(int s)
29 {
30     bool inq[MAXN];
31     int cnt[MAXN];
32     queue<int> q;
33     Gnode *p;
34 
35     memset(inq, false, sizeof(inq));
36     memset(cnt, 0, sizeof(cnt));
37     for (int i = 1; i <= n; ++i)
38         d[i] = (i == s ? 0 : INF);
39     q.push(s);
40     inq[s] = true;
41     ++cnt[s];
42     
43     while (!q.empty())
44     {
45         int i = q.front();
46         q.pop();
47         inq[i] = false;
48         for (p = a[i]->next; p; p = p->next)
49         {
50             int j = p->v;
51             if (d[i] + p->w < d[j])
52             {
53                 d[j] = d[i] + p->w;
54                 if (!inq[j])
55                 {
56                     q.push(j);
57                     inq[j] = true;
58                     ++cnt[j];
59                     if (cnt[j] > n)
60                         return false;
61                 }
62             }
63         }
64     }
65     return true;
66 }
67 
68 int main()
69 {
70     freopen("g.in", "r", stdin);
71     freopen("g.out", "w", stdout);
72 
73     scanf("%d %d", &n, &m);
74     for (int i = 1; i <= n; ++i)
75     {
76         a[i] = new Gnode;
77         a[i]->next = NULL;
78     }
79     for (int i = 1; i <= m; ++i)
80     {
81         int x, y, w;
82         scanf("%d %d %d", &x, &y, &w);
83         add_edge(x, y, w);
84         add_edge(y, x, w);
85     }
86     if (bellman_ford(1))
87     {
88         for (int i = 1; i < n; ++i)
89             printf("%d ", d[i]);
90         printf("%d", d[n]);
91         putchar('\n');
92     }
93     else printf("Failded\n");

94 
95     return 0;
96 }