Time Limit: 1000MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u
Description
Input
Output
Sample Input
Sample Output
Hint
Description
某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
Output
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
Sample Input
复制代码
1
2
3
4
5
6
7
83 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2
Sample Output
复制代码
1
22 -1
复制代码
1
复制代码
1
复制代码
1解法一：Dijkstra算法
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69<pre class="html" name="code">#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <queue> #include <iostream> #include <algorithm> using namespace std; #define inf 1<<29 #define maxn 210 int maps[maxn][maxn],dis[maxn],vis[maxn]; int n,m; using namespace std; int dijkstra(int s,int t) { for(int i = 0;i < n;i++) { dis[i] = maps[s][i]; vis[i] = 0; } dis[s] = 0; vis[s] = 1; int temp,k; for(int i = 0;i < n;i++) { temp = inf; for(int j = 0;j < n;j++) { if(vis[j] == 0 && temp > dis[j]) { k = j; temp = dis[j]; } } if(temp == inf) break; vis[k] = 1; for(int j = 0;j < n;j++) { if(dis[j] > dis[k] + maps[k][j]) dis[j] = dis[k] + maps[k][j]; } } if(dis[t] == inf) return -1; else return dis[t]; } int main() { int a,b,x,s,t,ans; while(scanf("%d %d",&n,&m) != EOF) { for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) maps[i][j] = (i == j ? 0 : inf); while(m--) { scanf("%d %d %d",&a,&b,&x); if(x < maps[a][b]) maps[a][b] = maps[b][a] = x; } scanf("%d %d",&s,&t); ans = dijkstra(s,t); printf("%dn",ans); } return 0; }
复制代码
1
复制代码
1</pre></div><div class="textBG"><pre>
复制代码
1解法二：Floyd算法
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#include<set> #include<queue> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define Inf 1<<29 using namespace std; int main() { int n,m; int mp[100][100]; while(~scanf("%d%d",&n,&m)) { for(int i=0; i<n; i++) for(int j=1; j<=n; j++) mp[i][j] = (i==j? 0 : Inf); for(int i=0; i<m; i++) { int a,b,x; scanf("%d %d %d",&a,&b,&x); if(x < mp[a][b]) mp[a][b] = mp[b][a] = x; } for(int k=0; k<n; k++) { for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { if(i!=j && j!=k) { mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]); } } } } int s,t; scanf("%d%d",&s,&t); if(mp[s][t]==Inf) printf("-1n"); else printf("%dn",mp[s][t]); } return 0; }
复制代码
1解法三：Bellman-Ford（贝尔曼）算法
复制代码
1
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187#include<set> #include<queue> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define Inf 1<<29 using namespace std; int dis[206]; int vis[205]; struct node { int u; int v; int w; } q[205*205]; int n,m; void bellman_floyd(int s) { for(int i=0; i<=n; i++) { dis[i]=Inf; } dis[s]=0; for(int i=1; i<=n; i++) { for(int j=1; j<=2*m+1; j++) { if(dis[q[j].u]+q[j].w<dis[q[j].v]) dis[q[j].v]=dis[q[j].u]+q[j].w; } }return ; } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=1; i<=2*m; i+=2) { scanf("%d%d%d",&q[i].u, &q[i].v, &q[i].w); q[i+1].v=q[i].u; q[i+1].u=q[i].v; q[i+1].w=q[i].w; } int t,w; scanf("%d%d",&t,&w); bellman_floyd(t); if(dis[w]==Inf) printf("-1n"); else printf("%dn",dis[w]); memset(q,0,sizeof(q)); } return 0; }解法四：SPFA复制代码#include<set> #include<queue> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn = 205; vector<pair<int ,int> >E[maxn]; int n,m; int d[maxn],inq[maxn]; void init() { for(int i=0; i<maxn; i++) E[i].clear(); for(int i=0; i<maxn; i++)inq[i]=0; for(int i=0; i<maxn; i++) d[i]=1e9; } int main() { while(cin>>n>>m) { init(); for(int i=0; i<m; i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); E[x].push_back(make_pair(y,z)); E[y].push_back(make_pair(x,z)); } int s,t; scanf("%d%d",&s,&t); queue<int> Q; Q.push(s),d[s]=0,inq[s]=1; while(!Q.empty()) { int now =Q.front(); Q.pop(); inq[now]=0; for(int i=0; i<E[now].size(); i++) { int v = E[now][i].first; if(d[v]>d[now]+E[now][i].second) { d[v]=d[now]+E[now][i].second; if(inq[v]==1) continue; inq[v]=0; Q.push(v); } } } if(d[t]==1e9) printf("-1n"); else printf("%dn",d[t]); } return 0; }
复制代码
1END！！！更新中。。。
最后
以上就是壮观硬币最近收集整理的关于HDU 1874 畅通工程续 （Floyd, Dijkstra，Bellman-Ford，SPFA）的全部内容，更多相关HDU内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复