A1111 Online Map (30 分)

题目地址：https://pintia.cn/problem-sets/994805342720868352/problems/994805358663417856

我的思路和这篇文章一样：https://blog.csdn.net/qq_30490125/article/details/50898531
题意要求我们找到确定起点和终点的最短路。
要求1：N,M分别表示道路交汇点的个数和道路的条数；
要求2：从题意理解oneWay代表该道路是单行道；
要求3：最短路不唯一，输出用时最短的那条；最短用时不唯一，输出经过道路交汇点最少的那条。
（道路不存在小于0的权值，用Dijkstra算法即可。）

程序步骤：
第一步、我们建立二维数组存储链接信息；
第二步、Dijkstra查找确定终点和起点的最短路（比一般的Dijkstra多添加了一个用时数组）；
第三步、取出上一步确定的路径，用栈将路径转化为正向存储；
第四步、由于题目要求我们求用时最短的最短路，将二维数组改造后即可用相同的Dijkstra算法来处理。
第五步、取出上一步确定的路径，用栈将路径转化为正向存储；
第六步、比较输出即可。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include<stack>
#include<queue>
using namespace std;

const int MaxN = 501;
const int Inf = 0x3fffffff;

struct node {
	int l=Inf;	//length
	int t=Inf;	//time
};

//N is  the total number of streets intersections on a map
//M is the number of streets
int N, M;
node G[MaxN][MaxN];
int dis[MaxN], path[MaxN];
bool vis[MaxN];
int tim[MaxN],inter[MaxN];		//到各个顶点花费时间, intersection岔路口

void PrintN(vector<int> a) {
	for (int i = 0; i < a.size(); i++) {
		cout << a[i];
		if (i < a.size() - 1)
			cout << " -> ";
	}
	cout << endl;
}

//Find shortest path, return the length
int Dijkstra_s(int v1,int v2, vector<int> &short_p) {
	fill(dis, dis + MaxN, Inf);
	fill(tim, tim + MaxN, Inf);
	fill(path, path + MaxN, -1);
	fill(vis, vis + MaxN, false);

	dis[v1] = 0;
	tim[v1] = 0;
	for (int ii = 0; ii < N; ii++) {
		//找未访问的distance最小的结点u
		int u = -1, MIN = Inf;
		for (int i = 0; i < N; i++) {
			if (dis[i] < MIN && vis[i] == false) {
				u = i;
				MIN = dis[i];
			}
		}
		if (u == -1)
			break;
		vis[u] = true;


		//以u为中转更新dis
		for (int j = 0; j < N; j++) {
			if (vis[j] == false && G[u][j].l!=Inf) {
				if (dis[j] > dis[u] + G[u][j].l) {
					dis[j] = dis[u] + G[u][j].l;
					tim[j] = tim[u] + G[u][j].t;
					path[j] = u;
				}
				//长度相同，时间更短
				else if (dis[j] == dis[u] + G[u][j].l && tim[j] > tim[u] + G[u][j].t) {
					dis[j] = dis[u] + G[u][j].l;
					tim[j] = tim[u] + G[u][j].t;
					path[j] = u;
				}
			}
		}

	}

	//求最短路径，写入short_p
	stack<int> s;
	int i = v2;
	while (i!= -1) {
		s.push(i);
		i = path[i];
	}
	while (!s.empty()) {
		short_p.push_back(s.top());
		s.pop();
	}

	return dis[v2];
}
//Find the fastest path, return the time
int Dijikstra_f(int v1,int v2, vector<int> &fast_p) {
	fill(inter, inter + MaxN, -1);
	fill(tim, tim + MaxN, Inf);
	fill(path, path + MaxN, -1);
	fill(vis, vis + MaxN, false);

	inter[v1] = 0;
	tim[v1] = 0;
	for (int ii = 0; ii < N; ii++) {
		//找未访问的tim最小的结点u
		int u = -1, MIN = Inf;
		for (int i = 0; i < N; i++) {
			if (tim[i] < MIN && vis[i] == false) {
				u = i;
				MIN = tim[i];
			}
		}
		if (u == -1)
			break;
		vis[u] = true;

		//以u为中转更新tim
		for (int j = 0; j < N; j++) {
			if (vis[j] == false && G[u][j].t != Inf) {
				if (tim[j] > tim[u] + G[u][j].t) {
					tim[j] = tim[u] + G[u][j].t;
					inter[j] = inter[u] + 1;
					path[j] = u;
				}
				//时间相同，交叉路口更少
				else if (tim[j] == tim[u] + G[u][j].t && inter[j]>inter[u]+1) {
					tim[j] = tim[u] + G[u][j].t;
					inter[j] = inter[u] + 1;
					path[j] = u;
				}
			}
		}

	}

	//求最短时间路径，写入fast_p
	stack<int> s;
	int i = v2;
	while (i!= -1) {
		s.push(i);
		i = path[i];
	}
	while (!s.empty()) {
		fast_p.push_back(s.top());
		s.pop();
	}

	return tim[v2];
}


int main() {
	//freopen("input.txt", "r", stdin);
	
	cin >> N >> M;
	
	for (int i = 0; i < M; i++) {
		int v1, v2, oneWay, l, t;
		cin >> v1 >> v2 >> oneWay >> l >> t;
		G[v1][v2].l = l;
		G[v1][v2].t = t;
		if (oneWay == 0) {
			G[v2][v1].l = l;
			G[v2][v1].t = t;
		}
	}
	int v1, v2;
	cin >> v1 >> v2;

	vector<int> short_p, fast_p;

	int d=Dijkstra_s(v1,v2,short_p);
	int t=Dijikstra_f(v1,v2,fast_p);

	//Output
	if (short_p != fast_p) {
		cout << "Distance = " << d << ": ";
		PrintN(short_p);
		cout << "Time = " << t << ": ";
		PrintN(fast_p);
	}
	else {
		cout << "Distance = " << d << "; Time = "<< t << ": ";
		PrintN(short_p);
	}

	
	return 0;
}
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