隨筆檔案

距離NOIP 2012復(fù)賽還有8天！
   從博客園的博客轉(zhuǎn)移到C++博客的第一篇博客。
   用優(yōu)先隊(duì)列（堆）實(shí)現(xiàn)的Dijkstra算法，最短路問(wèn)題中的正權(quán)圖適用，對(duì)于稠密圖計(jì)算比較優(yōu)秀。
   為了方便起見(jiàn)，我把pair<int, int>定義一個(gè)pii類型，并且定義了一個(gè)二元的優(yōu)先隊(duì)列，first代表起始節(jié)點(diǎn)到此節(jié)點(diǎn)的距離，second表示該節(jié)點(diǎn)的編號(hào)。存儲(chǔ)圖的方式我采用了指針實(shí)現(xiàn)的鄰接表。
   這份代碼的核心代碼不多，只有20多行，STL雖然用了vector、priority_queue、pair，但是相信沒(méi)有-o2的優(yōu)化下效率還是有保證的，可能pair會(huì)稍微慢一點(diǎn)。
   下面是我的代碼：
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <utility>
 4 #include <queue>
 5 using namespace std;
 6 
 7 #define maxn 10008
 8 #define INF 10000008
 9 
10 typedef struct G_NODE
11 {
12     int u, v, w;
13     struct G_NODE *next;
14 } Gnode;
15 
16 int n, m, d[maxn];
17 Gnode *a[maxn];
18 
19 void add_edge(int x, int y, int c)
20 {
21     Gnode *p = new Gnode;
22     p->u = x;
23     p->v = y;
24     p->w = c;
25     p->next = a[x]->next;
26     a[x]->next = p;
27 }
28 
29 void init_g()
30 {
31     scanf("%d %d", &n, &m);
32     for (int i = 1; i <= n; ++i)
33     {
34         a[i] = new Gnode;
35         a[i]->next = NULL;
36     }
37     for (int i = 0; i < m; ++i)
38     {
39         int x, y, c;
40         scanf("%d %d %d", &x, &y, &c);
41         add_edge(x, y, c);
42         add_edge(y, x, c);
43     }
44 }
45 
46 typedef pair<int, int> pii;
47 priority_queue<pii, vector<pii>, greater<pii> > q;
48 bool done[maxn];
49 
50 void dijkstra(int s)
51 {
52     Gnode *p;
53 
54     memset(done, false, sizeof(done));
55     for (int i = 1; i <= n; ++i)
56         d[i] = (i == s ? 0 : INF);
57     
58     q.push(make_pair(d[s], s));
59     while (!q.empty())
60     {
61         pii u = q.top();
62         q.pop();
63         int x = u.second;
64         if (done[x])
65             continue;
66         for (p = a[x]->next; p; p = p->next) if (d[p->v] > d[x] + p->w)
67         {
68             d[p->v] = d[x] + p->w;
69             q.push(make_pair(d[p->v], p->v));
70         }
71     }
72 }
73 
74 int main()
75 {
76     freopen("g.in", "r", stdin);
77     freopen("g.out", "w", stdout);
78 
79     init_g();
80     dijkstra(1);
81     for (int i = 1; i <= n; ++i)
82         printf("%d ", d[i]);
83     printf("\n");
84 
85     return 0;
86 }