PTA甲级考试真题练习111——1111 Online Map
程序员文章站
2022-06-11 18:04:01
...
题目
思路
使用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];
}
}
上一篇: 关键词选择原则及经验技巧小结
下一篇: Windows平台 微秒级 延时程序
推荐阅读
-
PTA甲级考试真题练习111——1111 Online Map
-
PTA甲级考试真题练习22——1022 Digital Library
-
PTA甲级考试真题练习18——1018 Public Bike Management
-
PTA甲级考试真题练习20——1020 Tree Traversals
-
PTA甲级考试真题练习30——1030 Travel Plan
-
PTA甲级考试真题练习17——1017 Queueing at Bank
-
PTA甲级考试真题练习8——1008 Elevator
-
PTA甲级考试真题练习23——1023 Have Fun with Numbers
-
PTA甲级考试真题练习5——1005 Spell It Right
-
PTA甲级考试真题练习11——1011 World Cup Betting