2013寒假ACM集训

2013寒假ACM集训_最短路

一、单源最短路

1、正权

dijkstra

2、任意权

2、1 bellman-ford

2、2 spfa

二、任意点之间最短路

floyd

三、最短路的应用：差分约束系统

参考模板

http://www.toposort.com/blog/shortest-path.html

贴一个新的最新的 spfa模板:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <queue>
 7 #include <algorithm>
 8 #include <vector>
 9 #define LL __int64
10 const int maxm = 2e6 + 10;
11 const int maxn = 5e5 + 10;
12 const int INF = 1<<28;
13 using namespace std;
14 int cnt, head[maxn], d[maxn], vis[maxn], n, m;
15 
16 struct node
17 {
18     int v, w, next;
19 }edge[2*maxm];
20 
21 void add(int u, int v, int w)
22 {
23     edge[cnt].v = v;
24     edge[cnt].w = w;
25     edge[cnt].next = head[u];
26     head[u] = cnt++;
27 };
28 
29 void spfa(int s)
30 {
31     queue<int>q;
32     int i, u, v;
33     for(i = 0; i <= n; i++)
34         d[i] = INF;
35     d[s] = 0;
36 
37     q.push(s);
38 
39     vis[s] = 1;
40     while(!q.empty())
41     {
42         u = q.front();
43         q.pop();
44         vis[u] = 0;
45         for(i = head[u]; i != -1; i = edge[i].next)
46         {
47             v=edge[i].v;
48             if(d[u] + edge[i].w < d[v])
49             {
50                 d[v] = d[u] + edge[i].w;
51                 if(!vis[v])
52                 {
53                     vis[v] = 1;
54                     q.push(v);
55                 }
56             }
57         }
58     }
59 };
60 int main()
61 {
62     int  i;
63     int a, b, w;
64     int s, t;
65     while(~scanf("%d%d", &n, &m))
66     {
67         cnt = 0;
68         memset(head, -1, sizeof(head));
69         memset(vis, 0, sizeof(vis));
70         for(i = 0; i < m; i++)
71         {
72             scanf("%d%d%d", &a, &b, &w);
73             add(a, b, w);
74             add(b, a, w);
75         }
76         scanf("%d%d", &s, &t);
77         spfa(s);
78         printf("%d\n", d[t]);
79     }
80 }