posts - 6,comments - 4,trackbacks - 0

 

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 *= new Gnode;
21     p->= x;
22     p->= y;
23     p->= 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, falsesizeof(inq));
36     memset(cnt, 0sizeof(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->< 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 }

 

posted on 2012-11-09 13:29 molasses 阅读(994) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理