最短路专题(不定期更新)

模板

1、spfa+SLF+LLL优化

 1 bool spfa()
 2 {//寻找s到t的最短路，dis数组记录点i到s的距离，vis数组表示是否被访问，cnt数组判环
 3     for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = false;
 4     dis[s] = 0, vis[s] = true;
 5     deque<int>q;
 6     q.push_back(s);
 7     int tot = 1;
 8     long long sum = dis[s];
 9     while (!q.empty())
10     {
11         int u = q.front();
12         while (1ll*dis[u] * tot > sum)
13         {
14             q.pop_front();
15             q.push_back(u);
16             u = q.front();
17         }
18         q.pop_front();
19         vis[u] = false;
20         tot--;
21         sum -= dis[u];
22         if (u == t)continue;
23         for (int i = Head[u]; i != -1; i = edge[i].next)
24         {
25             int v = edge[i].to, w = edge[i].w;
26             if (dis[u] + w < dis[v])
27             {
28                 dis[v] = dis[u] + w;
29                 if (!vis[v])
30                 {
31                     vis[v] = true;
32                     if (!q.empty())
33                     {
34                         int tmp = q.front();
35                         if (dis[v] < dis[tmp]) q.push_front(v);
36                         else q.push_back(v);
37                     }
38                     else q.push_back(v);
39                     tot++;
40                     sum += dis[v];
41                     cnt[v]++;
42                     if (cnt[v] > n) return false;
43                 }
44             }
45         }
46     }
47     return true;
48 }

View Code

2、堆+Dij

pair

 1 #define Pii pair<int,int>
 2 priority_queue<Pii, vector<Pii>, greater<Pii> >pq;
 3 void dij()
 4 {//堆优化,寻找s到t的最短路，dis数组记录点i到s的距离
 5     for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = false;
 6     dis[s] = 0;
 7     pq.push(make_pair(dis[s], s));
 8     while (!pq.empty())
 9     {
10         Pii cur = pq.top();
11         pq.pop();
12         int u = cur.second;
13         for (int i = Head[u]; i != -1; i = edge[i].next)
14         {
15             int v = edge[i].to, w = edge[i].w;
16             if (dis[v] > dis[u] + w)
17             {
18                 dis[v] = dis[u] + w;
19                 pq.push(make_pair(dis[v], v));
20             }
21         }
22     }
23 }

View Code

结构体

 1 struct node
 2 {
 3     int w, dis, t;
 4     node(int ww=0,int dd=0,int tt=0):w(ww),dis(dd),t(tt){}
 5     friend bool operator>(const node&n1, const node&n2)
 6     {
 7         return n1.dis > n2.dis;
 8     }
 9 };
10 void dij()
11 {//堆优化,寻找s到t的最短路，dis数组记录点i到s的距离
12     for (int i = 1; i <= n; i++) dis[i] = INF;
13     priority_queue<node, vector<node>, greater<node> >pq;
14     dis[s] = 0;
15     pq.push(node(-1,0,s));
16     while (!pq.empty())
17     {
18         node cur = pq.top();
19         pq.pop();
20         int u = cur.t;
21         for (int i = Head[u]; i != -1; i = edge[i].next)
22         {
23             int v = edge[i].to, w = edge[i].w;
24             if (w == cur.w) w = 0;
25             else w = 1;
26             if (dis[v] > dis[u] +w)
27             {
28                 dis[v] = dis[u] + w;
29                 pq.push(node(edge[i].w,dis[v],v));
30             }
31         }
32     }
33 }

View Code

3、dfs求有向无环图DAG中s到t的最短路

 1 int dfs(int u,int D)
 2 {//dis[i]表示i到终点的最短距离，dis数组初始化为INF
 3     if (dis[u] != INF) return dis[u];
 4     if (u == D)return dis[D]=0;
 5     int &tans = dis[u];
 6     for (int i = Head[u]; i != -1; i = edge[i].next)
 7     {
 8         int to = edge[i].to, w = edge[i].w;
 9         int cur=dfs(to, D);
10         if(cur!=INF) tans= min(tans, cur+ w);
11     }
12     return tans;
13 }

View Code

题目

1、Til the Cows Come Home POJ 2387

　　题意：找到从N到1的最短路径。

　　思路：SPFA。

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 using namespace std;
 5 const int maxn = 1010;
 6 const int INF = 0x7fffffff;
 7 int n, t;
 8 struct node
 9 {
10     int to;
11     int length;
12     node(int tt=0,int ll=0):to(tt),length(ll){ }
13 };
14 vector<node>mp[maxn];
15 int dis[maxn];
16 bool vis[maxn];
17 int cnt[maxn];
18 
19 bool SPFA(int root)
20 {
21     memset(vis, 0, sizeof(vis));
22     memset(cnt, 0, sizeof(cnt));
23     for (int i = 1; i <= n; i++) dis[i] = INF;
24     dis[root] = 0, cnt[root] = 1, vis[root] = true;
25     queue<int>q;
26     q.push(root);
27     while (!q.empty())
28     {
29         int u = q.front();
30         q.pop();
31         vis[u] = false;
32         int sz = mp[u].size();
33         for (int i = 0; i < sz; i++)
34         {
35             int v = mp[u][i].to,len = mp[u][i].length;
36             if (dis[u] + len < dis[v])
37             {
38                 dis[v] = dis[u] + len;
39                 if (!vis[v])
40                 {
41                     q.push(v);
42                     vis[v] = true;
43                     cnt[v]++;
44                     if (cnt[v] > n)return false;
45                 }
46             }
47         }
48     }
49     return true;
50 }
51 void Run()
52 {
53     for (int i = 0; i <= n; i++) mp[i].clear();
54     for (int i = 0; i < t; i++)
55     {
56         int u, v, l;
57         scanf("%d%d%d", &u, &v, &l);
58         mp[u].push_back(node(v, l));
59         mp[v].push_back(node(u, l));
60     }
61     SPFA(n);
62     printf("%d
", dis[1]);
63 }
64 int main()
65 {
66     while (~scanf("%d%d", &t, &n))
67     {
68         Run();
69     }
70     return 0;
71 }

View Code

2、POJ 2253 Frogger

　　题意：求从第一块石头到第二块石头的最大权值的最小值。

　　思路：SPFA扩展，dis[j] = min(dis[j], max(dis[MinNum], len))。注意初始化。

 1 //从1到2的路径所经过的最大权值的最小值
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 210;
 7 const double INF = 1e9;
 8 int n;
 9 double dis[maxn];
10 bool vis[maxn];
11 int pre[maxn];
12 double ans;
13 struct node
14 {
15     int x;
16     int y;
17 }stones[maxn];
18 void dijkstra(int start)
19 {
20     memset(vis, 0, sizeof(vis));
21     for (int i = 0; i < n; i++)
22         dis[i] = INF;
23     dis[start] = 0;
24     for (int i = 1; i <= n; i++)
25     {
26         int MinNum;
27         double Min = INF;
28         for (int j = 0; j < n; j++)
29             if (!vis[j] && dis[j]<Min)
30             {
31                 MinNum = j;
32                 Min = dis[j];
33             }
34         vis[MinNum] = true;
35         for (int j = 0; j < n; j++)
36         {
37             double len = sqrt(1.0*(stones[j].x - stones[MinNum].x)*(stones[j].x - stones[MinNum].x) + (stones[j].y - stones[MinNum].y)*(stones[j].y - stones[MinNum].y));
38             //dis[j] = min(dis[j], max(dis[MinNum], len));//dis[j]为从0号石头到第j号石头所有通路中最长边中的最小边
39             if (!vis[j]&&max(dis[MinNum], len) < dis[j]) dis[j] = max(dis[MinNum], len);
40         }
41     }
42 }
43 int main()
44 {
45     int Case = 1;
46     while (~scanf("%d", &n))
47     {
48         if (n == 0)break;
49         for (int i = 0; i < n; i++)
50         {
51             scanf("%d%d", &stones[i].x, &stones[i].y);
52         }
53         dijkstra(0);
54         printf("Scenario #%d
", Case);
55         printf("Frog Distance = %.3lf

", dis[1]);
56         Case++;
57     }
58     return 0;
59 }

View Code

3、poj 1797 Heavy Transportation

　　题意：求1到n的路径的最小权值的最大值。

　　思路：最短路拓展，dis[v] = max(dis[v],min(dis[u],len)).注意初始化。

  1 //求1到n的路径的最小权值的最大值
  2 #include<iostream>
  3 #include<vector>
  4 #include<queue>
  5 #include<algorithm>
  6 using namespace std;
  7 const int maxn = 1010;
  8 const int INF = 0x7fffffff;
  9 int n, m,Case;
 10 struct node
 11 {
 12     int to;
 13     int length;
 14     node(int tt = 0, int ll = 0) :to(tt), length(ll)
 15     {
 16     }
 17 };
 18 vector<node>mp[maxn];
 19 int dis[maxn];
 20 bool vis[maxn];
 21 int cnt[maxn];
 22 int ans;
 23 bool SPFA(int root)
 24 {
 25     memset(vis, 0, sizeof(vis));
 26     memset(cnt, 0, sizeof(cnt));
 27     memset(dis, 0, sizeof(dis));
 28     dis[root] =INF, cnt[root] = 1, vis[root] = true;
 29     queue<int>q;
 30     q.push(root);
 31     while (!q.empty())
 32     {
 33         int u = q.front();
 34         q.pop();
 35         vis[u] = false;
 36         int sz = mp[u].size();
 37         for (int i = 0; i < sz; i++)
 38         {
 39             int v = mp[u][i].to, len = mp[u][i].length;
 40             if (min(dis[u],len) > dis[v])
 41             {
 42                 dis[v] = min(dis[u],len);
 43                 if (!vis[v])
 44                 {
 45                     q.push(v);
 46                     vis[v] = true;
 47                     cnt[v]++;
 48                     if (cnt[v] > n)return false;
 49                 }
 50             }
 51         }
 52     }
 53     return true;
 54 }
 55 void Dij(int root)
 56 {
 57     memset(vis, 0, sizeof(vis));
 58     memset(dis, 0, sizeof(dis));
 59     int sz = mp[root].size();
 60     for (int i = 0; i < sz; i++)
 61     {
 62         dis[mp[root][i].to] = mp[root][i].length;
 63     }
 64     vis[1] = true;//标记点1已经访问过  
 65     for (int i = 1; i <= n - 1; i++)
 66     {
 67         int maxx = 0,u=root;
 68         for (int j = 1; j <= n; j++)
 69         {
 70             if (!vis[j] && dis[j]>maxx)
 71             {
 72                 maxx = dis[j];
 73                 u = j;
 74             }
 75         }
 76         vis[u] = true;
 77         int sz = mp[u].size();
 78         for (int j = 0; j < sz; j++)
 79         {
 80             int v = mp[u][j].to;
 81             if (!vis[v] && dis[v] < min(dis[u],mp[u][j].length))
 82                 dis[v] = min(dis[u], mp[u][j].length);
 83         }
 84     }
 85 }
 86 void Run()
 87 {
 88     for (int i = 0; i <= n; i++) mp[i].clear();
 89     for (int i = 0; i < m; i++)
 90     {
 91         int u, v, l;
 92         scanf("%d%d%d", &u, &v, &l);
 93         mp[u].push_back(node(v, l));
 94         mp[v].push_back(node(u, l));
 95     }
 96     //SPFA(1);
 97     Dij(1);
 98     printf("Scenario #%d:
", Case);
 99     printf("%d

",dis[n]);
100 }
101 int main()
102 {
103     int C;
104     Case = 1;
105     scanf("%d", &C);
106     while (C--)
107     {
108         scanf("%d%d", &n, &m);
109         Run();
110         Case++;
111     }
112     return 0;
113 }

View Code

4、poj 3268 Silver Cow Party

　　题意：每头牛从自己家最短路到X，再从X走最短路回家。求所有牛中走过距离的最大值。

　　思路：对其他点求一次到X的最短路，再从X求一次到其他各点的最短路。

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 using namespace std;
 5 const int maxn = 1010;
 6 const int INF = 0x7fffffff;
 7 int n, m,x;
 8 int sumdis[maxn];
 9 struct node
10 {
11     int to;
12     int length;
13     node(int tt = 0, int ll = 0) :to(tt), length(ll)
14     {
15     }
16 };
17 vector<node>mp[maxn];
18 int dis[maxn][maxn];
19 bool vis[maxn];
20 int cnt[maxn];
21 
22 bool SPFA(int root)
23 {
24     memset(vis, 0, sizeof(vis));
25     memset(cnt, 0, sizeof(cnt));
26     for (int i = 1; i <= n; i++) dis[root][i] = INF;
27     queue<int>q;
28     dis[root][root] = 0, vis[root] = true, cnt[root]++;
29     q.push(root);
30     while (!q.empty())
31     {
32         int u = q.front();
33         q.pop();
34         vis[u] = false;
35         int sz = mp[u].size();
36         for (int i = 0; i < sz; i++)
37         {
38             int v = mp[u][i].to, len = mp[u][i].length;
39             if (dis[root][u] + len < dis[root][v])
40             {
41                 dis[root][v] = dis[root][u] + len;
42                 if (!vis[v])
43                 {
44                     q.push(v);
45                     vis[v] = true;
46                     cnt[v]++;
47                     if (cnt[v] > n)return false;
48                 }
49             }
50         }
51     }
52     return true;
53 }
54 void Run()
55 {
56     for (int i = 0; i <= n; i++) mp[i].clear();
57     for (int i = 0; i < m; i++)
58     {
59         int u, v, l;
60         scanf("%d%d%d", &u, &v, &l);
61         mp[u].push_back(node(v, l));
62     }
63     int maxl=0;
64     for (int i = 1; i <= n; i++)
65     {
66         if (i == x)continue;
67         SPFA(i);
68         sumdis[i] = dis[i][x];
69     }
70     SPFA(x);
71     for (int i = 1; i <= n; i++)
72     {
73         if (i == x) continue;
74         sumdis[i] += dis[x][i];
75         maxl = max(maxl, sumdis[i]);
76     }
77     printf("%d
",maxl);
78 }
79 int main()
80 {
81     while (~scanf("%d%d%d", &n, &m,&x))
82     {
83         Run();
84     }
85     return 0;
86 }

View Code

5、POJ 1860 Currency Exchange

　　题意：给出货币之间的汇率兑换，问是否能经过几次兑换后，其得到的货币比原先要多。

　　思路：SPFA判正环。

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 using namespace std;
 5 const int maxn = 110;
 6 const int INF = 0x7fffffff;
 7 int n, m, s;
 8 double v;
 9 struct node
10 {
11     int to;
12     double r;
13     double c;
14     node(int tt = 0,double rr=0,double cc=0) :to(tt),r(rr),c(cc)
15     {
16     }
17 };
18 vector<node>mp[maxn];
19 double dis[maxn];
20 bool vis[maxn];
21 int cnt[maxn];
22 
23 bool SPFA(int root)
24 {
25     memset(vis, 0, sizeof(vis));
26     memset(cnt, 0, sizeof(cnt));
27     memset(dis, 0, sizeof(dis));
28     dis[root] = v, cnt[root] = 1, vis[root] = true;
29     queue<int>q;
30     q.push(root);
31     while (!q.empty())
32     {
33         int u = q.front();
34         q.pop();
35         vis[u] = false;
36         int sz = mp[u].size();
37         for (int i = 0; i < sz; i++)
38         {
39             int v = mp[u][i].to;
40             double r = mp[u][i].r;
41             double c = mp[u][i].c;
42             if (dis[v]<(dis[u]-c)*r)
43             {
44                 dis[v] = (dis[u] - c)*r;
45                 if (!vis[v])
46                 {
47                     q.push(v);
48                     vis[v] = true;
49                     cnt[v]++;
50                     if (cnt[v] > n)return true;
51                 }
52             }
53         }
54     }
55     return false;
56 }
57 void Run()
58 {
59     for (int i = 0; i <= n; i++) mp[i].clear();
60     for (int i = 0; i < m; i++)
61     {
62         int u, v;
63         double ruv, cuv, rvu, cvu;
64         scanf("%d%d%lf%lf%lf%lf", &u, &v, &ruv,&cuv,&rvu,&cvu);
65         mp[u].push_back(node(v, ruv,cuv));
66         mp[v].push_back(node(u, rvu,cvu));
67     }
68     if (SPFA(s)) printf("YES
");
69     else printf("NO
");
70 }
71 int main()
72 {
73     while (~scanf("%d%d%d%lf", &n, &m,&s,&v))
74     {
75         Run();
76     }
77     return 0;
78 }

View Code

6、POJ 3259 Wormholes

　　题意：给出一些无向边，从一点走到另一点需要花费t时间；还有一些黑洞，能使人从一点到另一点并且返回到t时间前。问能否遇到以前的自己。

　　思路：SPFA判负环。

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 using namespace std;
 5 const int maxn = 600;
 6 const int INF = 0x7fffffff;
 7 int n, m, w;
 8 double v;
 9 struct node
10 {
11     int to;
12     int len;
13     node(int tt = 0,int ll=0) :to(tt),len(ll)
14     {
15     }
16 };
17 vector<node>mp[maxn];
18 double dis[maxn];
19 bool vis[maxn];
20 int cnt[maxn];
21 
22 bool SPFA(int root)
23 {
24     memset(vis, 0, sizeof(vis));
25     memset(cnt, 0, sizeof(cnt));
26     for (int i = 0; i <= n; i++) dis[i] = INF;
27     dis[root] = 0, cnt[root] = 1, vis[root] = true;
28     queue<int>q;
29     q.push(root);
30     while (!q.empty())
31     {
32         int u = q.front();
33         q.pop();
34         vis[u] = false;
35         int sz = mp[u].size();
36         for (int i = 0; i < sz; i++)
37         {
38             int v = mp[u][i].to;
39             int len = mp[u][i].len;
40             if (dis[u]+len<dis[v])
41             {
42                 dis[v] = dis[u] + len;
43                 if (!vis[v])
44                 {
45                     q.push(v);
46                     vis[v] = true;
47                     cnt[v]++;
48                     if (cnt[v] > n)return true;
49                 }
50             }
51         }
52     }
53     return false;
54 }
55 void Run()
56 {
57     for (int i = 0; i <= n; i++) mp[i].clear();
58     for (int i = 0; i < m; i++)
59     {
60         int u, v, l;
61         scanf("%d%d%d", &u, &v, &l);
62         mp[u].push_back(node(v,l));
63         mp[v].push_back(node(u,l));
64     }
65     for (int j = 0; j < w; j++)
66     {
67         int u, v, l;
68         scanf("%d%d%d", &u, &v, &l);
69         l = -l;
70         mp[u].push_back(node(v, l));
71     }
72     if (SPFA(1)) printf("YES
");
73     else printf("NO
");
74 }
75 int main()
76 {
77     int C;
78     scanf("%d", &C);
79     while (C--)
80     {
81         scanf("%d%d%d", &n, &m, &w);
82         Run();
83     }
84     return 0;
85 }

View Code

7、poj1502 - MPI Maelstrom

　　题意：求从节点1到其他节点的最短路的最大值。

　　思路：SPFA。

 1 #include<iostream>
 2 #include<queue>
 3 #include<vector>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 using namespace std;
 7 int n;
 8 const int maxn = 110;
 9 const int INF = 0x7fffffff;
10 struct node
11 {
12     int to;
13     int len;
14     node(int tt = 0,int ll=0):to(tt),len(ll){ }
15 };
16 vector<node>mp[maxn];
17 bool vis[maxn];
18 int cnt[maxn];
19 int pre[maxn];
20 int dis[maxn];
21 bool SPFA(int root)
22 {
23     memset(vis, 0, sizeof(vis));
24     memset(cnt, 0, sizeof(cnt));
25     for (int i = 0; i <= n; i++) dis[i] = INF, pre[i] = root;
26     dis[root] = 0, vis[root] = true, cnt[root]++;
27     queue<int>q;
28     q.push(root);
29     while (!q.empty())
30     {
31         int u = q.front();
32         q.pop();
33         vis[u] = false;
34         int sz = mp[u].size();
35         for (int i = 0; i < sz; i++)
36         {
37             int v = mp[u][i].to;
38             int len = mp[u][i].len;
39             if (dis[u] + len < dis[v])
40             {
41                 dis[v] = dis[u] + len;
42                 if (!vis[v])
43                 {
44                     vis[v] = true;
45                     q.push(v);
46                     cnt[v]++;
47                     if (cnt[v] > n)return false;
48                 }
49             }
50         }
51     }
52     return true;
53 }
54 void Run()
55 {
56     char s[25];
57     for (int i = 0; i <= n; i++) mp[i].clear();
58     for (int i = 2; i <= n; i++)
59     {
60         for (int j = 1; j < i; j++)
61         {
62             scanf("%s", s);
63             if (s[0] != 'x')
64             {
65                 int v = atoi(s);
66                 mp[i].push_back(node(j, v));
67                 mp[j].push_back(node(i, v));
68             }
69         }
70     }
71     SPFA(1);
72     int ans = 0;
73     for (int i = 1; i <= n; i++)
74     {
75         ans = max(ans, dis[i]);
76     }
77     printf("%d
", ans);
78 }
79 int main()
80 {
81     while (~scanf("%d", &n))
82     {
83         Run();
84     }
85     return 0;
86 }

View Code

8、POJ 3660 Cow Contest

　　题意：对于N头牛，给出一些两两比赛的结果，问最多有几头牛的名次可以确定。

　　思路：Floyd拓展，根据传递性，判断两两之间的胜负。

 1 #include<iostream>
 2 #include<memory.h>
 3 using namespace std;
 4 int n, m;
 5 const int maxn = 110;
 6 int dis[maxn][maxn];
 7 void Run()
 8 {
 9     memset(dis, 0, sizeof(dis));
10     for (int i = 0; i < m; i++)
11     {
12         int winner, failer;
13         scanf("%d%d", &winner, &failer);
14         dis[winner][failer] = 1;
15         dis[failer][winner] = -1;
16     }
17     //类Floyd
18     for (int k = 1; k <= n; k++)
19     {
20         for (int i = 1; i <= n; i++)
21         {
22             for (int j = 1; j <= n; j++)
23             {
24                 if (dis[i][k] == dis[k][j] && (dis[i][k] == 1 || dis[i][k] == -1))
25                 {//闭包传递性
26                     dis[i][j] = dis[i][k];
27                 }
28             }
29         }
30     }
31     int ans = 0;
32     for (int i = 1; i <= n; i++)
33     {
34         int ct = 0;
35         for (int j = 1; j <= n; j++)
36         {
37             if (dis[i][j] != 0) ct++;
38         }
39         if (ct == n - 1) ans++;
40     }
41     printf("%d
", ans);
42 }
43 int main()
44 {
45     while (~scanf("%d%d", &n, &m))
46     {
47         Run();
48     }
49     return 0;
50 }

View Code

9、HDU 1217 Arbitrage

　　题意：给出一些货币之间的汇率，问能否进行套汇？即通过不断兑换货币使得最后自己钱比初始多。

　　思路：SPFA判正环

 1 #include<iostream>
 2 #include<map>
 3 #include<string>
 4 #include<vector>
 5 #include<queue>
 6 using namespace std;
 7 int n,m;
 8 const int maxn = 35;
 9 map<string, int>M;
10 struct node
11 {
12     int to;
13     double r;
14     node(int tt=0,double rr=0):to(tt),r(rr){ }
15 };
16 vector<node>mp[maxn];
17 bool vis[maxn];
18 int cnt[maxn];
19 double dis[maxn];
20 bool SPFA()
21 {
22     memset(vis, 0, sizeof(vis));
23     memset(cnt, 0, sizeof(cnt));
24     memset(dis, 0, sizeof(dis));
25     dis[1] = 1, vis[1] = true, cnt[1]++;
26     queue<int>q;
27     q.push(1);
28     while (!q.empty())
29     {
30         int u = q.front();
31         q.pop();
32         vis[u] = false;
33         int sz = mp[u].size();
34         for (int i = 0; i < sz; i++)
35         {
36             int v = mp[u][i].to;
37             double rt = mp[u][i].r;
38             double tv = dis[u] * rt;
39             if (tv> dis[v])
40             {
41                 dis[v] = dis[u] * rt;
42                 if (!vis[v])
43                 {
44                     q.push(v);
45                     vis[v] = true;
46                     cnt[v]++;
47                     if (cnt[v] > n)return true;
48                 }
49             }
50         }
51     }
52     return false;
53 }
54 int main()
55 {
56     int Case = 1;
57     while (~scanf("%d", &n))
58     {
59         if (n == 0) break;
60         for (int i = 0; i <= n; i++) mp[i].clear();
61         string s;
62         M.clear();
63         cin.get();
64         for (int i = 0; i < n; i++)
65         {
66             getline(cin, s);
67             M[s] = i + 1;
68         }
69         scanf("%d", &m);
70         string a, b;
71         double rt;
72         for (int i = 0; i < m; i++)
73         {
74             cin >> a >> rt >> b;
75             int ida = M[a];
76             int idb = M[b];
77             mp[ida].push_back(node(idb, rt));
78         }
79         if (SPFA()) printf("Case %d: Yes
", Case);
80         else printf("Case %d: No
", Case);
81         Case++;
82     }
83     return 0;
84 }

View Code

10、POJ 1511 HDU1535 Invitation Cards

　　题意：先从1到其他各点，在从其他各点回到1.求总共最小花费。

　　思路：通过逆向建边即只需通过两次SPFA即可求出答案。

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 using namespace std;
 5 int p, q;
 6 const int maxp = 1000010;
 7 const int INF = 0x7fffffff;
 8 bool vis[maxp];
 9 int cnt[maxp];
10 int pre[maxp];
11 int dis[maxp];
12 long long sum;
13 struct node
14 {
15     int to;
16     int fee;
17     node(int tt=0,int ff=0):to(tt),fee(ff){ }
18 };
19 vector<node>mp[maxp];
20 struct points
21 {
22     int from;
23     int to;
24     int v;
25 }pp[maxp];
26 bool SPFA(int root)
27 {
28     for (int i = 0; i <= p; i++)
29     {
30         dis[i] = INF;
31         pre[i] = root;
32         cnt[i] = 0;
33         vis[i] = false;
34     }
35     queue<int>q;
36     q.push(root);
37     dis[root]=0,cnt[root] = 1, vis[root] = true;
38     while (!q.empty())
39     {
40         int u = q.front();
41         q.pop();
42         vis[u] = false;
43         int sz = mp[u].size();
44         for (int i = 0; i < sz; i++)
45         {
46             int v = mp[u][i].to;
47             int ff = mp[u][i].fee;
48             if (dis[u] + ff < dis[v])
49             {
50                 dis[v] = dis[u] + ff;
51                 if (!vis[v])
52                 {
53                     vis[v] = true;
54                     cnt[v]++;
55                     q.push(v);
56                     if (cnt[v] > p)return false;
57                 }
58             }
59         }
60     }
61     return true;
62 }
63 void RSet()
64 {
65     for (int i = 0; i <= p; i++) mp[i].clear();
66     for (int i = 0; i < q; i++)
67     {
68         mp[pp[i].to].push_back(node(pp[i].from, pp[i].v));
69     }
70 }
71 int main()
72 {
73     int t;
74     scanf("%d", &t);
75     while (t--)
76     {
77         scanf("%d%d", &p, &q);
78         for (int i = 0; i <= p; i++) mp[i].clear();
79         for (int i = 0; i < q; i++)
80         {
81             int u, v, f;
82             scanf("%d%d%d", &u, &v, &f);
83             mp[u].push_back(node(v, f));
84             pp[i].from = u, pp[i].to = v, pp[i].v = f;
85         }
86         sum = 0;
87         SPFA(1);
88         for (int i = 2; i <= p; i++) sum += dis[i];
89         RSet();
90         SPFA(1);
91         for (int i = 2; i <= p; i++) sum += dis[i];
92         printf("%lld
", sum);
93     }
94 
95 
96     return 0;
97 }

View Code

11、POJ 3159 Candies（差分约束+栈SPFA）

　　题意：给出若干对（A，B，C），B的糖果不能比A多C，求第N个人最多比第1个人多多少？

　　思路：B-A<=C,差分约束，建立从A到B的有向边，权值为C。通过模拟栈来代替队列，否则TLE，同时用边表代替vector邻接表。

 1 #include<iostream>
 2 using namespace std;
 3 int n, m;
 4 const int maxn = 30100;
 5 const int INF = 0x7ffffff;
 6 struct eg
 7 {
 8     int to,next;
 9     int v;
10 }Edge[150100];
11 int head[maxn];
12 
13 bool vis[maxn];
14 int cnt[maxn];
15 int dis[maxn];
16 
17 int stk[maxn], top;//模拟栈
18 bool SPFA(int root)
19 {
20     for (int i = 0; i <= n; i++) dis[i] = INF;
21     memset(vis, 0, sizeof(vis));
22     memset(cnt, 0, sizeof(cnt));
23     dis[root] = 0, vis[root] = true, cnt[root]++;
24     top = 0;
25     stk[top++] = root;
26     while (top)
27     {
28         int u = stk[--top];
29         vis[u] = false;
30         for (int i = head[u]; i!=-1; i=Edge[i].next)
31         {
32             int v = Edge[i].to;
33             int vv = Edge[i].v;
34             if (dis[u] + vv < dis[v])
35             {
36                 dis[v] = dis[u] + vv;
37                 if (!vis[v])
38                 {
39                     vis[v] = true;
40                     cnt[v]++;
41                     stk[top++] = v;
42                     if (cnt[v] > n)return false;
43                 }
44             }
45         }
46     }
47     return true;
48 }
49 int main()
50 {
51     while (~scanf("%d%d", &n, &m))
52     {
53         memset(head, -1, sizeof(head));
54         for (int i = 0; i < m; i++)
55         {
56             int u, v, f;
57             scanf("%d%d%d", &u, &v, &f);
58             //v不能比u超过f个糖果：v-u<=f
59             Edge[i].to =v, Edge[i].v = f,Edge[i].next=head[u];
60             head[u] = i;
61         }
62         SPFA(1);//求v(n)-v(1)<=?
63         printf("%d
", dis[n]);
64     }
65     return 0;
66 }

View Code

12、POJ 2502 Subway

　　题意：给出家和学校的位置，再给出若干条地铁线路所经站点的位置，给出步行和地铁的速度，求从家到学校的最短时间。

　　思路：预处理图：只有同一线路的相邻地铁站点才能通过地铁，否则步行。SPFA。

 1 #include<iostream>
 2 #include<queue>
 3 #include<cmath>
 4 using namespace std;
 5 const int maxn = 210;
 6 const double INF = 1e9;
 7 int n;
 8 struct node
 9 {
10     int x;
11     int y;
12     node(int xx=0,int yy=0):x(xx),y(yy){ }
13 };
14 node points[maxn];
15 double dis[maxn];
16 double D[maxn][maxn];
17 bool vis[maxn];
18 int cnt[maxn];
19 int id;
20 bool SPFA(int root)
21 {
22     for (int i = 0; i <= id; i++) dis[i] = INF;
23     memset(vis, 0, sizeof(vis));
24     queue<int>q;
25     q.push(root);
26     dis[root] = 0, vis[root] = true, cnt[root] = 1;
27     while (!q.empty())
28     {
29         int u = q.front();
30         q.pop();
31         vis[u] = false;
32         for (int i = 1; i <= id; i++)
33         {
34             if (dis[u] + D[u][i] < dis[i])
35             {
36                 dis[i] = dis[u] + D[u][i];
37                 if (!vis[i])
38                 {
39                     vis[i] = true;
40                     cnt[i]++;
41                     q.push(i);
42                     if (cnt[i] > id)return false;
43                 }
44             }
45         }
46     }
47     return true;
48 }
49 int main()
50 {
51     //freopen("in.txt", "r", stdin);
52     double v1 = 40000.0 / 60.0;
53     double v2 = 10000.0 / 60.0;
54     while (~scanf("%d%d%d%d", &points[1].x, &points[1].y, &points[2].x, &points[2].y))
55     {
56         memset(D, 0, sizeof(D));
57         id = 2;
58         bool isfirst = true;
59         int tx, ty;
60         while (~scanf("%d%d", &tx, &ty))
61         {
62             if (tx == -1 && ty == -1)
63             {
64                 isfirst = true;
65                 continue;
66             }
67             if (isfirst)
68             {
69                 isfirst = false;
70                 id++;
71                 points[id].x = tx, points[id].y = ty;
72             }
73             else
74             {
75                 id++;
76                 points[id].x = tx, points[id].y = ty;
77                 D[id][id - 1]=D[id - 1][id] = sqrt(1.0*(points[id].x - points[id - 1].x)*(points[id].x - points[id - 1].x) + (points[id].y - points[id - 1].y)*(points[id].y - points[id - 1].y))/v1;
78             }
79         }
80         for (int i = 1; i <= id; i++)
81         {
82             for (int j = i+1; j <= id; j++)
83             {
84                 if (D[i][j] == 0)
85                 {
86                     D[i][j]=D[j][i]= sqrt(1.0*(points[i].x - points[j].x)*(points[i].x - points[j].x) + (points[i].y - points[j].y)*(points[i].y - points[j].y)) / v2;
87                 }
88             }
89         }//以上预处理各点间的距离，只有相邻车站才能用地铁，否则都为步行
90         SPFA(1);
91         printf("%.0lf
", dis[2]);
92     }
93     return 0;
94 }

View Code

13、POJ 1062 昂贵的聘礼

　　题意：探险家需要给酋长若干钱币，如果他能够找来一些其他物品能够得到优惠，同时如果探险家和某个人交易后，阶级超过限制的人不会再和他交易。问最少的花费。

　　思路：把探险家和所有的人看成一个点，原价看成是探险家到其他人的路径的权值，优惠为其他人之间路径的权值。最后求从探险家到酋长的最短路。不过需要根据阶级限制枚举能够交易的人，最后取min。

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 using namespace std;
 5 int M, N;
 6 const int maxn = 110;
 7 const int INF = 0x7fffffff;
 8 struct node
 9 {
10     int to;
11     int fee;
12     node(int tt=0,int ff=0):to(tt),fee(ff){ }
13 };
14 int lvl[maxn];
15 vector<node>mp[maxn];
16 int dis[maxn];
17 int cnt[maxn];
18 bool vis[maxn];
19 bool SPFA(int root, int limitl, int limitr)
20 {
21     memset(vis, 0, sizeof(vis));
22     memset(cnt, 0, sizeof(cnt));
23     for (int i = 0; i <= N; i++) dis[i] = INF;
24     dis[root] = 0, vis[root] = true, cnt[root]++;
25     queue<int>q;
26     q.push(root);
27     while (!q.empty())
28     {
29         int u = q.front();
30         q.pop();
31         int sz = mp[u].size();
32         for (int i = 0; i < sz; i++)
33         {
34             int v = mp[u][i].to;
35             int fee = mp[u][i].fee;
36             if (lvl[v]<limitl || lvl[v]>limitr)continue;
37             if (dis[u] + fee < dis[v])
38             {
39                 dis[v] = dis[u] + fee;
40                 if (!vis[v])
41                 {
42                     vis[v] = true;
43                     cnt[v]++;
44                     q.push(v);
45                     if (cnt[v] > N+1)return false;
46                 }
47             }
48         }
49         vis[u] = false;
50     }
51     return true;
52 }
53 int main()
54 {
55     while (~scanf("%d%d", &M, &N))
56     {
57         for (int i = 0; i <= N; i++) mp[i].clear();
58         for (int i = 1; i <= N; i++)
59         {
60             int cost, level, x;
61             scanf("%d%d%d", &cost, &level, &x);
62             mp[0].push_back(node(i, cost));
63             lvl[i] = level;
64             for (int j = 0; j < x; j++)
65             {
66                 int u, cost2;
67                 scanf("%d%d", &u, &cost2);
68                 mp[u].push_back(node(i, cost2));
69             }
70         }
71         int ans = INF;
72         for (int limit = lvl[1] - M; limit <= lvl[1]; limit++)
73         {
74             SPFA(0,limit,limit+M);
75             ans = min(ans, dis[1]);
76         }
77         printf("%d
", ans);
78     }
79     return 0;
80 }

View Code

13、POJ 1847 Tram

　　题意：给出若干结点和哪些结点连通，每个结点有个初始朝向，如果要换轨，则变换次数+1.求最少的变换次数。

　　思路：SPFA，若两节点之间无需换轨，权值为0，否则权值置为1.SPFA

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 using namespace std;
 5 int N, A, B;
 6 const int maxn = 110;
 7 const int INF = 0x7fffffff;
 8 struct node
 9 {
10     int to;
11     int fee;
12     node(int tt=0,int ff=0):to(tt),fee(ff){ }
13 };
14 vector<node>mp[maxn];
15 int dis[maxn];
16 bool vis[maxn];
17 int cnt[maxn];
18 int pre[maxn];
19 bool SPFA(int root)
20 {
21     memset(vis, 0, sizeof(vis));
22     memset(cnt, 0, sizeof(cnt));
23     for (int i = 0; i <= N; i++) dis[i] = INF, pre[i] = root;
24     dis[root] = 0, vis[root] = true, cnt[root]++;
25     queue<int>q;
26     q.push(root);
27     while (!q.empty())
28     {
29         int u = q.front();
30         q.pop();
31         vis[u] = false;
32         int sz = mp[u].size();
33         for (int i = 0; i < sz; i++)
34         {
35             int v = mp[u][i].to;
36             int f = mp[u][i].fee;
37             if (dis[u] + f < dis[v])
38             {
39                 dis[v] = dis[u] + f;
40                 if (!vis[v])
41                 {
42                     vis[v] = true;
43                     cnt[v]++;
44                     q.push(v);
45                     if (cnt[v] > N)return false;
46                 }
47             }
48         }
49     }
50     return true;
51 }
52 int main()
53 {
54     while (~scanf("%d%d%d", &N, &A, &B))
55     {
56         for (int i = 0; i <= N; i++) mp[i].clear();
57         for (int i = 1; i <= N; i++)
58         {
59             int k;
60             scanf("%d", &k);
61             for (int j = 0; j < k; j++)
62             {
63                 int to;
64                 scanf("%d", &to);
65                 if (j == 0)mp[i].push_back(node(to, 0));
66                 else mp[i].push_back(node(to, 1));
67             }
68         }
69         SPFA(A);
70         if(dis[B]!=INF)printf("%d
", dis[B]);
71         else printf("-1
");
72     }
73     return 0;
74 }

View Code

14、lightOJ 1074 Extended Traffic

　　题意：每个路口有个拥挤度，从一个路口到另一个路口的时间为目标路口的拥挤度减去起点处的拥挤度的3次方。求从1到给定路口的最小时间。

　　思路：SPFA。注意负环的存在，如果存在负环，则标记负环中的点和从负环能到达的点。

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 #include<memory.h>
 5 #include<cstdio>
 6 using namespace std;
 7 const int maxn = 210;
 8 const int INF = 0x7fffffff;
 9 int n, m, q;
10 int busy[maxn];
11 struct node
12 {
13     int to;
14     int dd;
15     node(int tt=0,int d=0):to(tt),dd(d){ }
16 };
17 vector<node>mp[maxn];
18 bool vis[maxn];
19 bool isfu[maxn];
20 int dis[maxn];
21 int cnt[maxn];
22 bool SPFA(int root)
23 {
24     memset(vis, 0, sizeof(vis));
25     memset(cnt, 0, sizeof(cnt));
26     memset(isfu, 0, sizeof(isfu));
27     for (int i = 0; i <= n; i++) dis[i] = INF;
28     dis[root] = 0, cnt[root]++, vis[root] = true;
29     queue<int>q;
30     q.push(root);
31     while (!q.empty())
32     {
33         int u = q.front();
34         q.pop();
35         vis[u] = false;
36         int sz = mp[u].size();
37         for (int i = 0; i < sz; i++)
38         {
39             int v = mp[u][i].to;
40             int ff = mp[u][i].dd;
41             if (isfu[v])continue;
42             if (dis[u] + ff < dis[v])
43             {
44                 dis[v] = dis[u] + ff;
45                 if (!vis[v])
46                 {
47                     q.push(v);
48                     cnt[v]++;
49                     vis[v] = true;
50                     if (cnt[v] > n)isfu[v] = true;
51                 }
52             }
53         }
54 
55     }
56     return true;
57 }
58 int main()
59 {
60     int t;
61     int Case = 1;
62     scanf("%d", &t);
63     while (t--)
64     {
65         scanf("%d", &n);
66         for (int i = 0; i <= n; i++) mp[i].clear();
67         for (int i = 1; i <= n; i++) scanf("%d", &busy[i]);
68         scanf("%d", &m);
69         for (int i = 0; i < m; i++)
70         {
71             int u, v;
72             scanf("%d%d", &u, &v);
73             int len = (busy[v] - busy[u])*(busy[v] - busy[u])*(busy[v] - busy[u]);
74             mp[u].push_back(node(v, len));
75         }
76         SPFA(1);
77         scanf("%d", &q);
78         printf("Case %d:
", Case++);
79         for (int i = 0; i < q; i++)
80         {
81             int des;
82             scanf("%d", &des);
83             if (isfu[des] || dis[des] == INF || dis[des] < 3)printf("?
");
84             else printf("%d
",dis[des]);
85         }
86     }
87     return 0;
88 }

View Code

15、hdu 4725 The Shortest Path in Nya Graph

　　题意：每个点都有各自所在的层次，相邻层之间穿越要c时间，还有一些桥，相互之间到达要花费时间。求从1到N的最小时间。

　　思路：SPFA，关键在于构建边。

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 using namespace std;
 5 int n, m, c;
 6 const int maxn = 100010;
 7 const int INF = 0x7fffffff;
 8 int layer[maxn];
 9 struct node
10 {
11     int to;
12     int val;
13     node(int tt=0,int vv=0):to(tt),val(vv){ }
14 };
15 vector<node>mp[maxn*2];
16 
17 bool vis[maxn*2];
18 int dis[maxn*2];
19 int cnt[maxn*2];
20 int cntl[maxn];
21 bool SPFA(int root)
22 {
23     memset(vis, 0, sizeof(vis));
24     memset(cnt, 0, sizeof(cnt));
25     for (int i = 0; i <= n*2; i++) dis[i] = INF;
26     dis[root] = 0, cnt[root]++, vis[root] = true;
27     queue<int>q;
28     q.push(root);
29     while (!q.empty())
30     {
31         int u = q.front();
32         q.pop();
33         vis[u] = false;
34         int sz = mp[u].size();
35         for (int i = 0; i < sz; i++)
36         {
37             int v = mp[u][i].to;
38             int f = mp[u][i].val;
39             if (dis[u] + f < dis[v])
40             {
41                 dis[v] = dis[u] + f;
42                 if (!vis[v])
43                 {
44                     vis[v] = true;
45                     q.push(v);
46                     cnt[v]++;
47                     if (cnt[v] > n)return false;
48                 }
49             }
50         }
51     }
52     return true;
53 }
54 int main()
55 {
56     int t;
57     scanf("%d", &t);
58     int Case = 1;
59     while (t--)
60     {
61         memset(cntl, 0, sizeof(cntl));
62         scanf("%d%d%d", &n, &m, &c);
63         for (int i = 0; i <= n*2; i++) mp[i].clear();
64         for (int i = 1; i <= n; i++)
65         {
66             scanf("%d", &layer[i]);
67             cntl[layer[i]]++;
68         }
69         for (int i = 1; i < n; i++)
70         {//相邻层建边
71             if (cntl[i] && cnt[i + 1])
72             {
73                 mp[n + i].push_back(node(n + i + 1, c));
74                 mp[n + 1 + i].push_back(node(n + i, c));
75             }
76         }
77         for (int i = 1; i <= n; i++)
78         {
79             mp[n + layer[i]].push_back(node(i, 0));//从点所在层到该点建边（不能反向，否则同一层的点最后距离都为0）
80             if (layer[i] > 1) mp[i].push_back(node(n + layer[i] - 1, c));//从该点到其下一层建边
81             if (layer[i] < n) mp[i].push_back(node(n + layer[i] + 1, c));//从该点到其上一层建边
82         }
83         for (int i = 0; i < m; i++)
84         {
85             int u,v, w;
86             scanf("%d%d%d", &u, &v, &w);
87             mp[u].push_back(node(v, w));
88             mp[v].push_back(node(u, w));
89         }
90         SPFA(1);
91         if (dis[n] == INF) printf("Case #%d: -1
",Case++);
92         else printf("Case #%d: %d
", Case++, dis[n]);
93     }
94     return 0;
95 }

View Code