您的位置: 首页  >  文章  >  PAT-ADVANCED1111——Online Map

PAT-ADVANCED1111——Online Map

分类: 文章 • 2024-08-10 14:07:46

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805358663417856

题目描述：

PAT-ADVANCED1111——Online Map

题目翻译：

1111 在线地图

输入你所在的位置和目的地，一张在线地图会推荐几条路线。现在你的任务是给用户推荐两条路线：第一条是最短的，第二条是最快的。题目保证对任何请求一定存在一条路径。

输入格式：

每个输入文件包含一个测试用例。在每个测试用例中，第一行有2个正整数：N(2 <= N <= 500)和M，分别表示地图上十字路口的数量和街道的数量。接下来的M行，每一行按下述格式描述一条街道：

V1 V2 one-way length time

V1和V2是街道两个端点的标记，范围在0 ~ N - 1之间。如果one-way是1，说明这条街道是单向的，只能从V1到V2，如果是0则是双向的。length是这条街道的长度。time是通过这条街道所花费的时间。

最后提供了起点和终点的信息。

输出格式：

对每个测试用例，第一行按以下格式输出从起点到终点的最短路径信息，其中D表示最短距离：

Distance = D: source -> v1 -> ... -> destination

接下来的一行按以下格式输出从起店到终点的最快路径信息，其中T表示最短时间：

Time = T: source -> w1 -> ... -> destination

如果最短路径不唯一，输出最短路径中最快的那条路径，题目保证这样的路径唯一。如果最快路径不唯一，输出经过最少十字路口的路径，题目保证这样的路径唯一。

如果最短路径和最快路径相同，按以下格式在一行中输出信息：

Distance = D; Time = T: source -> u1 -> ... -> destination

输入样例1：

10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5

输出样例1：

Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5

输入样例2：

7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5

输出样例2：

Distance = 3; Time = 4: 3 -> 2 -> 5

知识点：Dijkstra算法、Bellman-Ford算法、SPFA算法、深度优先遍历

思路一：Dijkstra算法+深度优先遍历（邻接表实现）

分别以长度和时间为边权求两次Dijkstra算法+深度优先遍历即可。

注意点：

对于邻接表来说，要求AB的边权，我们需要遍历与A相连的所有端点才能找到B端点，这一方面邻接表不如邻接矩阵直接。

时间复杂度是O(N ^ 2)。空间复杂度是O(N + M)。

C++代码：

#include<iostream>
#include<vector>

using namespace std;

struct node {
	int v;	//端点编号
	int length;	//道路长度
	int time;	//道路时间
	node(int _v, int _length, int _time) : v(_v), length(_length), time(_time) {};	//构造函数
};

int N;	//十字路口数量
int M;	//道路数量
int source;
int destination;
int INF = 1000000000;
vector<node> graph[501];	//有向图
int d1[501];
int d2[501];
bool visited1[501] = {false};
bool visited2[501] = {false};
vector<int> pre1[501];
vector<int> pre2[501];
vector<int> tempPath1;
vector<int> tempPath2;
vector<int> path1;
vector<int> path2;
int optValue1 = INF;
int optValue2 = INF;

void dijkstra1(int s);
void dfs1(int nowVisit);
void dijkstra2(int s);
void dfs2(int nowVisit);

int main() {
	cin >> N >> M;
	int V1, V2, one_way, length, time;
	for(int i = 0; i < M; i++) {
		cin >> V1 >> V2 >> one_way >> length >> time;
		graph[V1].push_back(node(V2, length, time));
		if(one_way == 0) {
			graph[V2].push_back(node(V1, length, time));
		}
	}
	cin >> source >> destination;
	dijkstra1(source);
	dfs1(destination);
	dijkstra2(source);
	dfs2(destination);
	bool flag = true;
	if(path1.size() != path2.size()) {
		flag = false;
	} else {
		for(int i = 0; i < path1.size(); i++) {
			if(path1[i] != path2[i]) {
				flag = false;
				break;
			}
		}
	}
	if(flag) {
		cout << "Distance = " << d1[destination] << "; Time = " << d2[destination] << ": ";
		for(int i = path1.size() - 1; i >= 0; i--) {
			cout << path1[i];
			if(i != 0) {
				cout << " -> ";
			}
		}
		cout << endl;
	} else {
		cout <<"Distance = " << d1[destination] << ": ";
		for(int i = path1.size() - 1; i >= 0; i--) {
			cout << path1[i];
			if(i != 0) {
				cout << " -> ";
			}
		}
		cout << endl;
		cout <<"Time = " << d2[destination] << ": ";
		for(int i = path2.size() - 1; i >= 0; i--) {
			cout << path2[i];
			if(i != 0) {
				cout << " -> ";
			}
		}
		cout << endl;
	}
	return 0;
}

void dijkstra1(int s) {
	for(int i = 0; i < N; i++) {
		d1[i] = INF;
	}
	d1[s] = 0;
	for(int i = 0; i < N; i++) {
		int u = -1, min = INF;
		for(int j = 0; j < N; j++) {
			if(!visited1[j] && d1[j] < min) {
				min = d1[j];
				u = j;
			}
		}
		if(u == -1) {
			return;
		}
		visited1[u] = true;
		for(int j = 0; j < graph[u].size(); j++) {
			int v = graph[u][j].v;
			int length = graph[u][j].length;
			if(!visited1[v]) {
				if(d1[u] + length < d1[v]) {
					d1[v] = d1[u] + length;
					pre1[v].clear();
					pre1[v].push_back(u);
				} else if(d1[u] + length == d1[v]) {
					pre1[v].push_back(u);
				}
			}
		}
	}
}

void dfs1(int nowVisit) {
	tempPath1.push_back(nowVisit);
	if(nowVisit == source) {
		int value1 = 0;
		for(int i = tempPath1.size() - 1; i > 0; i--) {
			//对于邻接表求边权，需要遍历该点连接的所有点才能寻找到所要求的那条边的边权
			for(int j = 0; j < graph[tempPath1[i]].size(); j++){	
				if(graph[tempPath1[i]][j].v == tempPath1[i - 1]){
					value1 += graph[tempPath1[i]][j].time;
					break; 
				}
			}
		}
		if(value1 < optValue1) {
			optValue1 = value1;
			path1 = tempPath1;
		}
		tempPath1.pop_back();
		return;
	}
	for(int i = 0; i < pre1[nowVisit].size(); i++) {
		dfs1(pre1[nowVisit][i]);
	}
	tempPath1.pop_back();
}

void dijkstra2(int s) {
	for(int i = 0; i < N; i++) {
		d2[i] = INF;
	}
	d2[s] = 0;
	for(int i = 0; i < N; i++) {
		int u = -1, min = INF;
		for(int j = 0; j < N; j++) {
			if(!visited2[j] && d2[j] < min) {
				min = d2[j];
				u = j;
			}
		}
		if(u == -1) {
			return;
		}
		visited2[u] = true;
		for(int j = 0; j < graph[u].size(); j++) {
			int v = graph[u][j].v;
			int time = graph[u][j].time;
			if(!visited2[v]) {
				if(d2[u] + time < d2[v]) {
					d2[v] = d2[u] + time;
					pre2[v].clear();
					pre2[v].push_back(u);
				} else if(d2[u] + time == d2[v]) {
					pre2[v].push_back(u);
				}
			}
		}
	}
}

void dfs2(int nowVisit) {
	tempPath2.push_back(nowVisit);
	if(nowVisit == source) {
		int value2 = tempPath2.size();
		if(value2 < optValue2) {
			optValue2 = value2;
			path2 = tempPath2;
		}
		tempPath2.pop_back();
		return;
	}
	for(int i = 0; i < pre2[nowVisit].size(); i++) {
		dfs2(pre2[nowVisit][i]);
	}
	tempPath2.pop_back();
}

C++解题报告：

PAT-ADVANCED1111——Online Map

思路二：Bellman-Ford算法+深度优先遍历（邻接表实现）（测试点4会超时）

分别以长度和时间为边权求两次Bellman-Ford算法+深度优先遍历即可。

时间复杂度是O(N * M)。空间复杂度是O(N + M)。

C++代码：

#include<iostream>
#include<vector>
#include<set>

using namespace std;

struct node {
	int v;	//端点编号
	int length;	//道路长度
	int time;	//道路时间
	node(int _v, int _length, int _time) : v(_v), length(_length), time(_time) {};	//构造函数
};

int N;	//十字路口数量
int M;	//道路数量
int source;
int destination;
int INF = 1000000000;
vector<node> graph[501];	//有向图
int d1[501];
int d2[501];
set<int> pre1[501];
set<int> pre2[501];
vector<int> tempPath1;
vector<int> tempPath2;
vector<int> path1;
vector<int> path2;
int optValue1 = INF;
int optValue2 = INF;

bool bellmanFord1(int s);
void dfs1(int nowVisit);
bool bellmanFord2(int s);
void dfs2(int nowVisit);

int main() {
	cin >> N >> M;
	int V1, V2, one_way, length, time;
	for(int i = 0; i < M; i++) {
		cin >> V1 >> V2 >> one_way >> length >> time;
		graph[V1].push_back(node(V2, length, time));
		if(one_way == 0) {
			graph[V2].push_back(node(V1, length, time));
		}
	}
	cin >> source >> destination;
	bellmanFord1(source);
	dfs1(destination);
	bellmanFord2(source);
	dfs2(destination);
	bool flag = true;
	if(path1.size() != path2.size()) {
		flag = false;
	} else {
		for(int i = 0; i < path1.size(); i++) {
			if(path1[i] != path2[i]) {
				flag = false;
				break;
			}
		}
	}
	if(flag) {
		cout << "Distance = " << d1[destination] << "; Time = " << d2[destination] << ": ";
		for(int i = path1.size() - 1; i >= 0; i--) {
			cout << path1[i];
			if(i != 0) {
				cout << " -> ";
			}
		}
		cout << endl;
	} else {
		cout <<"Distance = " << d1[destination] << ": ";
		for(int i = path1.size() - 1; i >= 0; i--) {
			cout << path1[i];
			if(i != 0) {
				cout << " -> ";
			}
		}
		cout << endl;
		cout <<"Time = " << d2[destination] << ": ";
		for(int i = path2.size() - 1; i >= 0; i--) {
			cout << path2[i];
			if(i != 0) {
				cout << " -> ";
			}
		}
		cout << endl;
	}
	return 0;
}

bool bellmanFord1(int s) {
	for(int i = 0; i < N; i++) {
		d1[i] = INF;
	}
	d1[s] = 0;
	for(int i = 0; i < N - 1; i++) {
		for(int u = 0; u < N; u++) {
			for(int j = 0; j < graph[u].size(); j++) {
				int v = graph[u][j].v;
				int length = graph[u][j].length;
				if(d1[u] + length < d1[v]) {
					d1[v] = d1[u] + length;
					pre1[v].clear();
					pre1[v].insert(u);
				} else if(d1[u] + length == d1[v]) {
					pre1[v].insert(u);
				}
			}
		}
	}
	for(int u = 0; u < N; u++) {
		for(int j = 0; j < graph[u].size(); j++) {
			int v = graph[u][j].v;
			int length = graph[u][j].length;
			if(d1[u] + length < d1[v]) {
				return false;
			}
		}
	}
	return true;
}

void dfs1(int nowVisit) {
	tempPath1.push_back(nowVisit);
	if(nowVisit == source) {
		int value1 = 0;
		for(int i = tempPath1.size() - 1; i > 0; i--) {
			//对于邻接表求边权，需要遍历该点连接的所有点才能寻找到所要求的那条边的边权
			for(int j = 0; j < graph[tempPath1[i]].size(); j++) {
				if(graph[tempPath1[i]][j].v == tempPath1[i - 1]) {
					value1 += graph[tempPath1[i]][j].time;
					break;
				}
			}
		}
		if(value1 < optValue1) {
			optValue1 = value1;
			path1 = tempPath1;
		}
		tempPath1.pop_back();
		return;
	}
	set<int>::iterator it;
	for(it = pre1[nowVisit].begin(); it != pre1[nowVisit].end(); it++) {
		dfs1(*it);
	}
	tempPath1.pop_back();
}

bool bellmanFord2(int s) {
	for(int i = 0; i < N; i++) {
		d2[i] = INF;
	}
	d2[s] = 0;
	for(int i = 0; i < N - 1; i++) {
		for(int u = 0; u < N; u++) {
			for(int j = 0; j < graph[u].size(); j++) {
				int v = graph[u][j].v;
				int time = graph[u][j].time;
				if(d2[u] + time < d2[v]) {
					d2[v] = d2[u] + time;
					pre2[v].clear();
					pre2[v].insert(u);
				} else if(d2[u] + time == d2[v]) {
					pre2[v].insert(u);
				}
			}
		}
	}
	for(int u = 0; u < N; u++) {
		for(int j = 0; j < graph[u].size(); j++) {
			int v = graph[u][j].v;
			int time = graph[u][j].time;
			if(d2[u] + time < d2[v]) {
				return false;
			}
		}
	}
	return true;
}

void dfs2(int nowVisit) {
	tempPath2.push_back(nowVisit);
	if(nowVisit == source) {
		int value2 = tempPath2.size();
		if(value2 < optValue2) {
			optValue2 = value2;
			path2 = tempPath2;
		}
		tempPath2.pop_back();
		return;
	}
	set<int>::iterator it;
	for(it = pre2[nowVisit].begin(); it != pre2[nowVisit].end(); it++) {
		dfs2(*it);
	}
	tempPath2.pop_back();
}

C++解题报告：

PAT-ADVANCED1111——Online Map

思路三：SPFA算法+深度优先遍历（邻接表实现）

期望时间复杂度是O(kN)，其中k是一个常数，在很多情况下k不超过2，可见这个算法异常高效，并且经常性地优于堆优化的Dijkstra算法。空间复杂度是O(N + M)。

C++代码：

#include<iostream>
#include<vector>
#include<set>
#include<queue>

using namespace std;

struct node {
	int v;	//端点编号
	int length;	//道路长度
	int time;	//道路时间
	node(int _v, int _length, int _time) : v(_v), length(_length), time(_time) {};	//构造函数
};

int N;	//十字路口数量
int M;	//道路数量
int source;
int destination;
int INF = 1000000000;
vector<node> graph[501];	//有向图
int d1[501];
int d2[501];
set<int> pre1[501];
set<int> pre2[501];
vector<int> tempPath1;
vector<int> tempPath2;
vector<int> path1;
vector<int> path2;
int optValue1 = INF;
int optValue2 = INF;
bool inq1[501] = {false};
bool inq2[501] = {false};
int countInq1[501] = {0};
int countInq2[501] = {0};

bool spfa1(int s);
void dfs1(int nowVisit);
bool spfa2(int s);
void dfs2(int nowVisit);

int main() {
	cin >> N >> M;
	int V1, V2, one_way, length, time;
	for(int i = 0; i < M; i++) {
		cin >> V1 >> V2 >> one_way >> length >> time;
		graph[V1].push_back(node(V2, length, time));
		if(one_way == 0) {
			graph[V2].push_back(node(V1, length, time));
		}
	}
	cin >> source >> destination;
	spfa1(source);
	dfs1(destination);
	spfa2(source);
	dfs2(destination);
	bool flag = true;
	if(path1.size() != path2.size()) {
		flag = false;
	} else {
		for(int i = 0; i < path1.size(); i++) {
			if(path1[i] != path2[i]) {
				flag = false;
				break;
			}
		}
	}
	if(flag) {
		cout << "Distance = " << d1[destination] << "; Time = " << d2[destination] << ": ";
		for(int i = path1.size() - 1; i >= 0; i--) {
			cout << path1[i];
			if(i != 0) {
				cout << " -> ";
			}
		}
		cout << endl;
	} else {
		cout <<"Distance = " << d1[destination] << ": ";
		for(int i = path1.size() - 1; i >= 0; i--) {
			cout << path1[i];
			if(i != 0) {
				cout << " -> ";
			}
		}
		cout << endl;
		cout <<"Time = " << d2[destination] << ": ";
		for(int i = path2.size() - 1; i >= 0; i--) {
			cout << path2[i];
			if(i != 0) {
				cout << " -> ";
			}
		}
		cout << endl;
	}
	return 0;
}

bool spfa1(int s) {
	for(int i = 0; i < N; i++) {
		d1[i] = INF;
	}
	d1[s] = 0;
	queue<int> q;
	q.push(s);
	inq1[s] = true;
	countInq1[s]++;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		inq1[u] = false;
		for(int j = 0; j < graph[u].size(); j++) {
			int v = graph[u][j].v;
			int length = graph[u][j].length;
			if(d1[u] + length < d1[v]) {
				d1[v] = d1[u] + length;
				pre1[v].clear();
				pre1[v].insert(u);
				if(!inq1[v]) {
					q.push(v);
					inq1[v] = true;
					countInq1[v]++;
					if(countInq1[v] > N) {
						return false;
					}
				}
			} else if(d1[u] + length == d1[v]) {
				pre1[v].insert(u);
				if(!inq1[v]) {
					q.push(v);
					inq1[v] = true;
					countInq1[v]++;
					if(countInq1[v] > N) {
						return false;
					}
				}
			}
		}
	}
	return true;
}

void dfs1(int nowVisit) {
	tempPath1.push_back(nowVisit);
	if(nowVisit == source) {
		int value1 = 0;
		for(int i = tempPath1.size() - 1; i > 0; i--) {
			//对于邻接表求边权，需要遍历该点连接的所有点才能寻找到所要求的那条边的边权
			for(int j = 0; j < graph[tempPath1[i]].size(); j++) {
				if(graph[tempPath1[i]][j].v == tempPath1[i - 1]) {
					value1 += graph[tempPath1[i]][j].time;
					break;
				}
			}
		}
		if(value1 < optValue1) {
			optValue1 = value1;
			path1 = tempPath1;
		}
		tempPath1.pop_back();
		return;
	}
	set<int>::iterator it;
	for(it = pre1[nowVisit].begin(); it != pre1[nowVisit].end(); it++) {
		dfs1(*it);
	}
	tempPath1.pop_back();
}

bool spfa2(int s) {
	for(int i = 0; i < N; i++) {
		d2[i] = INF;
	}
	d2[s] = 0;
	queue<int> q;
	q.push(s);
	inq2[s] = true;
	countInq2[s]++;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		inq2[u] = false;
		for(int j = 0; j < graph[u].size(); j++) {
			int v = graph[u][j].v;
			int time = graph[u][j].time;
			if(d2[u] + time < d2[v]) {
				d2[v] = d2[u] + time;
				pre2[v].clear();
				pre2[v].insert(u);
				if(!inq2[v]){
					q.push(v);
					inq2[v] = true;
					countInq2[v]++;
					if(countInq2[v] > N){
						return false;
					}
				}
			} else if(d2[u] + time == d2[v]) {
				pre2[v].insert(u);
				if(!inq2[v]){
					q.push(v);
					inq2[v] = true;
					countInq2[v]++;
					if(countInq2[v] > N){
						return false;
					}
				}
			}
		}
	}
	return true;
}

void dfs2(int nowVisit) {
	tempPath2.push_back(nowVisit);
	if(nowVisit == source) {
		int value2 = tempPath2.size();
		if(value2 < optValue2) {
			optValue2 = value2;
			path2 = tempPath2;
		}
		tempPath2.pop_back();
		return;
	}
	set<int>::iterator it;
	for(it = pre2[nowVisit].begin(); it != pre2[nowVisit].end(); it++) {
		dfs2(*it);
	}
	tempPath2.pop_back();
}

C++解题报告：

PAT-ADVANCED1111——Online Map

 

相关推荐