L3-007. 天梯地图
时间限制
300 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越
本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。
输入格式：
输入在第一行给出两个正整数N（2 <= N <=500）和M，分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行，每行按如下格式给出一条道路的信息：
V1 V2 one-way length time
其中V1和V2是道路的两个端点的编号（从0到N-1）；如果该道路是从V1到V2的单行线，则one-way为1，否则为0；length是道路的长度；time是通过该路所需要的时间。最后给出一对起点和终点的编号。
输出格式：
首先按下列格式输出最快到达的时间T和用节点编号表示的路线：
Time = T: 起点 => 节点1 => ... => 终点
然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：
Distance = D: 起点 => 节点1 => ... => 终点
如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。
如果这两条路线是完全一样的，则按下列格式输出：
Time = T; Distance = D: 起点 => 节点1 => ... => 终点
输入样例1：复制代码
输出样例1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1710 15 0 1 0 1 1 8 0 0 1 1 4 8 1 1 1 5 4 0 2 3 5 9 1 1 4 0 6 0 1 1 7 3 1 1 2 8 3 1 1 2 2 5 0 2 2 2 1 1 1 1 1 5 0 1 3 1 4 0 1 1 9 7 1 1 3 3 1 0 2 5 6 3 1 2 1 5 3
复制代码
输入样例2:
1
2Time = 6: 5 => 4 => 8 => 3 Distance = 3: 5 => 1 => 3
复制代码
输出样例2:
1
2
3
4
5
6
7
8
9
10
117 9 0 4 1 1 1 1 6 1 3 1 2 6 1 1 1 2 5 1 2 2 3 0 0 1 1 3 1 1 3 1 3 2 1 2 1 4 5 0 2 2 6 5 1 2 1 3 5
复制代码
1Time = 3; Distance = 4: 3 => 2 => 5
复制代码
1
复制代码
1tips：很烦的一道 最短路问题，给的条件太多了....一开始尝试了用搜索，加了个小剪枝，最后一个测试点亦然超时。
复制代码
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
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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349复制代码#include<iostream> #include<cstring> #include<queue> #include<vector> using namespace std; int n,m,way,s,e; int tmp[510]; int l[510][510],t[510][510];//两点间的距离,时间 vector<int>g[550];//邻接关系 int dis[510];//到源点距离数组 int _ime[510];//到源点时间数组 const int inf=0x3f3f3f3f; int book1[510],book2[510]; vector<int>f1[510];//记录最短路径信息 vector<int>f2[510];//记录最快路径信息 vector<int>dans; //最终的最短输出路径 vector<int>tans;//最终的最快输出路径 struct node1{ int x,d; friend bool operator <(node1 n1,node1 n2) { return n1.d>n2.d; } }; struct node2{ int x,tt; friend bool operator <(node2 n1,node2 n2) { return n1.tt>n2.tt; } }; //堆优化的dijkstra()。求最短路 void dijkstra1() { memset(dis,0x3f,sizeof(dis)); memset(book1,0,sizeof(book1)); priority_queue<node1>q; q.push(node1{s,0}); dis[s]=0; while(!q.empty()) { node1 tmp=q.top();q.pop(); int x=tmp.x; if(book1[x])continue; book1[x]=1; for(int i=0;i<g[x].size();i++) { int nx=g[x][i]; if(dis[nx]>dis[x]+l[x][nx])//松弛并且记录前驱结点 { dis[nx]=dis[x]+l[x][nx]; q.push(node1{nx,dis[nx]}); f1[nx].clear(); //如果发现最短路，记得清楚以前保存的前驱结点 f1[nx].push_back(x); } else if(dis[nx]==dis[x]+l[x][nx]) { f1[nx].push_back(x);//最短路不唯一的情况 } } } } void dijkstra2() { memset(_ime,0x3f,sizeof(_ime)); memset(book2,0,sizeof(book2)); priority_queue<node2>qq; qq.push(node2{s,0}); _ime[s]=0; while(!qq.empty()) { node2 tmp=qq.top();qq.pop(); int x=tmp.x; if(book2[x])continue; book2[x]=1; for(int i=0;i<g[x].size();i++) { int nx=g[x][i]; if(_ime[nx]>_ime[x]+t[x][nx])//松弛并且记录前驱结点 { _ime[nx]=_ime[x]+t[x][nx]; qq.push(node2{nx,_ime[nx]}); f2[nx].clear(); f2[nx].push_back(x); } else if(_ime[nx]==_ime[x]+t[x][nx]) { f2[nx].push_back(x);//最短路不唯一的情况 } } } } int sz=inf; void dfs1(int x,int step) { tmp[step]=x; if(x==s) { if(step<sz) { sz=step; dans.clear(); for(int i=step;i>=1;i--)dans.push_back(tmp[i]); } return ; } for(int i=0;i<f1[x].size();i++) { dfs1(f1[x][i],step+1); } } int maxn=inf; void dfs2(int x,int step,int cnt) { tmp[step]=x; if(x==s) { if(cnt<maxn) { maxn=cnt; tans.clear(); for(int i=step;i>=1;i--)tans.push_back(tmp[i]); } return; } for(int i=0;i<f2[x].size();i++) { dfs2(f2[x][i],step+1,cnt+l[f2[x][i]][x]);//注意此处，f2[x][i][x]千万不能写反，因为可能有单行道路 } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y,way,len,_ime;cin>>x>>y>>way>>len>>_ime; l[x][y]=len; t[x][y]=_ime; g[x].push_back(y); if(!way)g[y].push_back(x),l[y][x]=len,t[y][x]=_ime; } cin>>s>>e; dijkstra1();//最短路 dfs1(e,1);//最短路径中途经结点数量最少的路径 dijkstra2();// 最快路 dfs2(e,1,0);//最快路径中最短的那条 if(tans==dans) { cout<<"Time = "<<_ime[e]<<"; Distance = "<<dis[e]<<": "; cout<<dans[0]; for(int i=1;i<dans.size();i++) { cout<<" => "<<dans[i]; } cout<<endl; } else{ cout<<"Time = "<<_ime[e]<<": "<<tans[0]; for(int i=1;i<tans.size();i++) { cout<<" => "<<tans[i]; } cout<<endl; cout<<"Distance = "<<dis[e]<<": "<<dans[0]; for(int i=1;i<dans.size();i++) { cout<<" => "<<dans[i]; } cout<<endl; } return 0; }
最后
以上就是无语胡萝卜最近收集整理的关于团体程序设计天梯赛 L3-007. 天梯地图（dijkstral+记录所有最短路径） L3-007. 天梯地图的全部内容，更多相关团体程序设计天梯赛内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复