Dijkstra（L3-007 天梯地图（30 分））

159 阅读 0 评论 105 点赞

我是靠谱客的博主搞怪水池，这篇文章主要介绍Dijkstra（L3-007 天梯地图（30 分）），现在分享给大家，希望可以做个参考。

原题链接
L3-007 天梯地图（30 分）
本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。

输入格式：
输入在第一行给出两个正整数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：
10 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
输出样例1：
Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3
输入样例2：
7 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
输出样例2：
Time = 3; Distance = 4: 3 => 2 => 5

分析:
这题目主要是是使用两次dij，“要求最快到达路径不唯一的时候，输出最短的路径”和“要求最短路径不唯一的时候，输出节点数最少的”。
我的解决办法是写两次dij，求最快到达路径时，用一个w记录同时的路程，在时间相等的情况下，选择w小的。同样的在求最短路径的时候，用一个num记录同时的节点数，在距离相等的情况下，选择num小的。

PS：可是，我提交完代码，发现第三个点过不了，看完别人都是用dfs搜素路径写的，我觉得我的思路也没有问题，不懂哪里出现bug，如果有眼惠聪颖的，请求指明。

相类似的题目有：
https://blog.csdn.net/caipengbenren/article/details/86585284
https://blog.csdn.net/caipengbenren/article/details/87939688

在这里插入图片描述

复制代码

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int N = 501;
const int INF = (1 << 30) - 2;
int len[N][N];
int tim[N][N];
int dij_le[N];
int dij_ti[N];
int w[N];
bool visit[N];
stack<int >ans_le;
stack<int >ans_ti;
int num[N + 1];
int n, m, s, d; //标记点的个数
void print(stack<int >a) {
int cnt = int(a.size());
for(int i = 1; i <= cnt; i++) {
cout << " " << a.top();
if(i != cnt) {
cout << " =>";
}
a.pop();
}
}
void dij_len() {
int pre[N + 1];
fill(visit, visit + N,false);
fill(dij_le, dij_le + N,INF);
fill(num, num + N, 1);
dij_le[s] = 0;
for (int i = 1; i <= n; i++) {
int x = -1, minn = INF;
for (int j = 0; j < n; j++) {
if (minn >= dij_le[j] && visit[j] == false) {
minn = dij_le[j];
x = j;
}
}
if(x == -1) break;
visit[x] = true;
for (int j = 0; j < n; j++) {
if (visit[j] == true || len[x][j] == INF) continue;
if (dij_le[j] > dij_le[x] + len[x][j]) {
dij_le[j] = dij_le[x] + len[x][j];
num[j] = num[x] + 1;
pre[j] = x;
} else if (dij_le[j] == dij_le[x] + len[x][j]) {
if (num[j] > num[x] + 1) {
num[j] = num[x] + 1;
pre[j] = x;
}
}
}
}
int flag = d;
while(flag != s) {
ans_le.push(flag);
flag = pre[flag];
}
ans_le.push(flag);
}
void dij_tim() {
int pre[N + 1];
fill(visit, visit + N, false);
fill(dij_ti, dij_ti + N, INF);
dij_ti[s] = 0;
for (int i = 1; i <= n; i++) {
int x = -1, minn = INF;
for (int j = 0; j < n; j++) {
if (minn > dij_ti[j] && visit[j] == false) {
minn = dij_ti[j];
x = j;
}
}
if(x == -1) break;
visit[x] = true;
for (int j = 0; j < n; j++) {
if (visit[j] == true || tim[x][j] == INF) continue;
if (dij_ti[j] > dij_ti[x] + tim[x][j]) {
dij_ti[j] = dij_ti[x] + tim[x][j];
pre[j] = x;
w[j] = w[x] + len[x][j];
} else if (dij_ti[j] == dij_ti[x] + tim[x][j]) {
if (w[j] > w[x] + len[x][i]) {
w[j] = w[x] + len[x][i];
pre[j] = x;
}
}
}
}
int flag = d;
while(flag != s) {
ans_ti.push(flag);
flag = pre[flag];
}
ans_ti.push(flag);
}
int main() {
cin >> n >> m;
fill(len[0], len[0] + N * N, INF);
fill(tim[0], tim[0] + N * N, INF);
for (int i = 1; i <= m; i++) {
int v1, v2, ow, l, t;
cin >> v1 >> v2 >> ow >> l >> t;
len[v1][v2] = l;
tim[v1][v2] = t;
if(ow == 0) {
len[v2][v1] = l;
tim[v2][v1] = t;
}
}
cin >> s >> d;
dij_len();
dij_tim();
if(ans_le != ans_ti) {
printf("Time = %d:",dij_ti[d]);
print(ans_ti);
printf("nDistance = %d:", dij_le[d]);
print(ans_le);
} else {
printf("Time = %d; Distance = %d:", dij_ti[d], dij_le[d]);
print(ans_ti);
}
}

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
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int N = 501;
const int INF = (1 << 30) - 2;
int len[N][N];
int tim[N][N];
int dij_le[N];
int dij_ti[N];
int w[N];
bool visit[N];
stack<int >ans_le;
stack<int >ans_ti;
int num[N + 1];
int n, m, s, d; //标记点的个数
void print(stack<int >a) {
int cnt = int(a.size());
for(int i = 1; i <= cnt; i++) {
cout << " " << a.top();
if(i != cnt) {
cout << " =>";
}
a.pop();
}
}
void dij_len() {
int pre[N + 1];
fill(visit, visit + N,false);
fill(dij_le, dij_le + N,INF);
fill(num, num + N, 1);
dij_le[s] = 0;
for (int i = 1; i <= n; i++) {
int x = -1, minn = INF;
for (int j = 0; j < n; j++) {
if (minn >= dij_le[j] && visit[j] == false) {
minn = dij_le[j];
x = j;
}
}
if(x == -1) break;
visit[x] = true;
for (int j = 0; j < n; j++) {
if (visit[j] == true || len[x][j] == INF) continue;
if (dij_le[j] > dij_le[x] + len[x][j]) {
dij_le[j] = dij_le[x] + len[x][j];
num[j] = num[x] + 1;
pre[j] = x;
} else if (dij_le[j] == dij_le[x] + len[x][j]) {
if (num[j] > num[x] + 1) {
num[j] = num[x] + 1;
pre[j] = x;
}
}
}
}
int flag = d;
while(flag != s) {
ans_le.push(flag);
flag = pre[flag];
}
ans_le.push(flag);
}
void dij_tim() {
int pre[N + 1];
fill(visit, visit + N, false);
fill(dij_ti, dij_ti + N, INF);
dij_ti[s] = 0;
for (int i = 1; i <= n; i++) {
int x = -1, minn = INF;
for (int j = 0; j < n; j++) {
if (minn > dij_ti[j] && visit[j] == false) {
minn = dij_ti[j];
x = j;
}
}
if(x == -1) break;
visit[x] = true;
for (int j = 0; j < n; j++) {
if (visit[j] == true || tim[x][j] == INF) continue;
if (dij_ti[j] > dij_ti[x] + tim[x][j]) {
dij_ti[j] = dij_ti[x] + tim[x][j];
pre[j] = x;
w[j] = w[x] + len[x][j];
} else if (dij_ti[j] == dij_ti[x] + tim[x][j]) {
if (w[j] > w[x] + len[x][i]) {
w[j] = w[x] + len[x][i];
pre[j] = x;
}
}
}
}
int flag = d;
while(flag != s) {
ans_ti.push(flag);
flag = pre[flag];
}
ans_ti.push(flag);
}
int main() {
cin >> n >> m;
fill(len[0], len[0] + N * N, INF);
fill(tim[0], tim[0] + N * N, INF);
for (int i = 1; i <= m; i++) {
int v1, v2, ow, l, t;
cin >> v1 >> v2 >> ow >> l >> t;
len[v1][v2] = l;
tim[v1][v2] = t;
if(ow == 0) {
len[v2][v1] = l;
tim[v2][v1] = t;
}
}
cin >> s >> d;
dij_len();
dij_tim();
if(ans_le != ans_ti) {
printf("Time = %d:",dij_ti[d]);
print(ans_ti);
printf("nDistance = %d:", dij_le[d]);
print(ans_le);
} else {
printf("Time = %d; Distance = %d:", dij_ti[d], dij_le[d]);
print(ans_ti);
}
}