欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA甲级考试真题练习111——1111 Online Map

程序员文章站 2022-06-11 18:04:01
...

题目

PTA甲级考试真题练习111——1111 Online Map

思路

使用Dijkstra即可,使用DFS最后一个测试点会超时

代码

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
const int nmax = 505;
const int inf = 2147483647;
int l[nmax][nmax],t[nmax][nmax];
int dis[nmax], dispre[nmax], weight[nmax], node[nmax],Time[nmax];
int n, m,src,tar;
int minl = inf, mint = inf;
int suml = 0, sumt = 0;
vector<int> vecl;
vector<int> vect;
bool visited[nmax];

void dj1() {
	for (int i = 0; i < n; ++i) {
		int	min_val = inf, u = -1;
		for (int j = 0; j < n; ++j) {
			if (!visited[j] && dis[j] < min_val) {
				min_val = dis[j];
				u = j;
			}
		}
		if (u == -1)
			break;
		visited[u] = true;
		for (int j = 0; j < n; ++j) {
			if (!visited[j] && l[u][j] != inf) {
				if (dis[u] + l[u][j] < dis[j]) {
					dis[j] = dis[u] + l[u][j];
					weight[j] = weight[u] + t[u][j];
					dispre[j] = u;
				}else if (dis[u] + l[u][j] == dis[j] && weight[u] + t[u][j] < weight[j]) {
					weight[j] = weight[u] + t[u][j];
					dispre[j] = u;
				}
			}
		}
	}
	int tmp = tar;
	while (tmp != src) {
		vecl.emplace_back(tmp);
		tmp = dispre[tmp];
	}
	vecl.emplace_back(src);
}
void dj2() {
	for (int i = 0; i < n; ++i) {
		int	min_val = inf, u = -1;
		for (int j = 0; j < n; ++j) {
			if (!visited[j] && Time[j] < min_val) {
				min_val = Time[j];
				u = j;
			}
		}
		if (u == -1)
			break;
		visited[u] = 1;
		for (int j = 0; j < n; ++j) {
			if (!visited[j] && t[u][j] != inf) {
				if (Time[u] + t[u][j] < Time[j]) {
					Time[j] = Time[u] + t[u][j];
					node[j] = node[u] + 1;
					dispre[j] = u;
				}else if (Time[u] + t[u][j] == Time[j] && node[u] + 1 < node[j]) {
					node[j] = node[u] + 1;
					dispre[j] = u;
				}
			}
		}
	}
	int tmp = tar;
	while (tmp != src) {
		vect.emplace_back(tmp);
		tmp = dispre[tmp];
	}
	vect.emplace_back(src);
}
int main()
{
	cin >> n >> m;
	memset(visited, 0, sizeof(visited));
	fill(l[0], l[0] + nmax * nmax, inf);
	fill(t[0], t[0] + nmax * nmax, inf);
	fill(dis, dis + n, inf);
	fill(weight, weight + n, inf);
	fill(Time, Time + n, inf);
	for (int i = 0; i < m; ++i) {
		int u, v, one_way;
		cin >> u >> v >> one_way;
		cin >> l[u][v] >> t[u][v];
		if (one_way == 0) {
			l[v][u] = l[u][v];
			t[v][u] = t[u][v];
		}
	}
	cin >> src>>tar;	
	dis[src] = 0;
	weight[src] = 0;
	dj1();
	memset(visited, 0, sizeof(visited));
	node[src] = 0;
	Time[src] = 0;
	dj2();
	if (vecl == vect) {
		cout << "Distance = " << dis[tar] << "; Time = " << weight[tar] << ": " << vecl[vecl.size()-1];
		for (int i = vecl.size()-2; i >= 0; --i)
			cout << " -> " << vecl[i];
	}else {
		cout << "Distance = " << dis[tar] <<": "<< vecl[vecl.size() - 1];
		for (int i = vecl.size() - 2; i >= 0; --i)
			cout << " -> " << vecl[i];
		cout << endl;
		cout << "Time = " << Time[tar] << ": " << vect[vect.size() - 1];
		for (int i = vect.size() - 2; i >= 0; --i)
			cout << " -> " << vect[i];
	}
}