随笔档案

距离NOIP 2012复赛还有8天！
   从博客园的博客转移到C++博客的第一篇博客。
   用优先队列（堆）实现的Dijkstra算法，最短路问题中的正权图适用，对于稠密图计算比较优秀。
   为了方便起见，我把pair<int, int>定义一个pii类型，并且定义了一个二元的优先队列，first代表起始节点到此节点的距离，second表示该节点的编号。存储图的方式我采用了指针实现的邻接表。
   这份代码的核心代码不多，只有20多行，STL虽然用了vector、priority_queue、pair，但是相信没有-o2的优化下效率还是有保证的，可能pair会稍微慢一点。
   下面是我的代码：
 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 }