posts - 6,comments - 4,trackbacks - 0

距离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 *= new Gnode;
22     p->= x;
23     p->= y;
24     p->= 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<intint> 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, falsesizeof(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 }


posted on 2012-11-02 12:05 molasses 阅读(2753) 评论(4)  编辑 收藏 引用

FeedBack:
# re: 使用优先队列的 Dijkstra 算法
2012-11-04 23:46 | Maigo
用stl挺耗空间的  回复  更多评论
  
# re: 使用优先队列的 Dijkstra 算法
2012-11-09 13:34 | Spix Mojo
是为了代码的可读性吧
有的时候显式的数据结构写起来太麻烦了
STL可以增强代码的可读性
@Maigo
  回复  更多评论
  
# re: 使用优先队列的 Dijkstra 算法
2015-11-19 00:03 | shop as roma
用stl挺耗空间的. 很赞同。 我的空间也是  回复  更多评论
  
# re: 使用优先队列的 Dijkstra 算法
2016-01-05 08:06 | Sleepless Loki
@shop as roma
我最近在研究Facebook的开源库,folly容器的效率比stl的更好。
https://github.com/facebook/folly/tree/master/folly  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理