PAT甲级1087All Roads Lead to Rome

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805379664297984

题解

题目要求

找到成本最低、快乐值总和最高的路径。优先找成本最低的,然后再找快乐值最高的,然后再找平均快乐值最高的。

  • 输入
    • N:正整数,[2,200],城市的数量
    • K:正整数,路径的数量
    • 起始城市的名称
    • N-1个城市的名字及其快乐值
    • K条路径
  • 输出
    • 成本最低的路径的数量
    • 成本
    • 快乐值总和
    • 平均快乐值(只输出整数部分)
    • 路径

解题思路

这是一道dijkstra+DFS的题,和PAT甲级1018Public Bike Management很类似,所以详细思路不再说明。

  • 用两个map将城市的名字和索引相互对应
  • 用dijkstra算法求出起始城市到所有城市的最短距离,并记录每个城市的前驱城市
  • 使用DFS求出路径(并计算、比较快乐值总和与平均值)

代码

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
// Problem: PAT Advanced 1087
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805379664297984
// Tags: 图 最短路 单源最短路 dijkstra BFS DFS

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

int n, k;
string startCity;

map<string, int> sti;
map<int, string> its;

const int INF = 9999999;
const int MAXN = 201;
int dis[MAXN][MAXN];
int minDis[MAXN];
bool visited[MAXN];
int happiness[MAXN];
vector<int> pre[MAXN];
vector<int> path;
vector<int> tempPath;
int ansHappinessSum = -INF, ansPathNum = 0;
double ansHappinessAve = -INF;

void dfs(int v){
tempPath.push_back(v);

if (v == 1){ // 到达起点
int happinessSum = 0;
for (auto iter = tempPath.begin(); iter != tempPath.end(); iter++)
happinessSum += happiness[*iter];
double happinessAve = happinessSum * 1.0 / (tempPath.size() - 1);
if (ansHappinessSum < happinessSum){
path = tempPath;
ansHappinessSum = happinessSum;
ansHappinessAve = happinessAve;
}
else if (ansHappinessSum == happinessSum && ansHappinessAve < happinessAve){
path = tempPath;
ansHappinessAve = happinessAve;
}
ansPathNum++;
tempPath.pop_back();
return ;
}

for (int i = 0; i < pre[v].size(); i++)
dfs(pre[v][i]);

tempPath.pop_back();
}

int main()
{
fill(dis[0], dis[0] + MAXN * MAXN, INF);
fill(minDis, minDis + MAXN, INF);

scanf("%d %d", &n, &k);
cin >> startCity;
sti[startCity] = 1;
its[1] = startCity;

string s;
int h;
for (int i = 2; i <= n; i++){
cin >> s;
sti[s] = i;
its[i] = s;
scanf("%d", &h);
happiness[i] = h;
}

string t;
for (int i = 0; i < k; i++){
cin >> s >> t;
scanf("%d", &dis[sti[s]][sti[t]]);
dis[sti[t]][sti[s]] = dis[sti[s]][sti[t]];
}

minDis[1] = 0;
for (int i = 1; i <= n; i++){
int tempMin = INF, u = -1;
for (int j = 1; j <= n; j++){
if (!visited[j] && tempMin > minDis[j]){
tempMin = minDis[j];
u = j;
}
}
if (u == -1) break;
visited[u] = true;

for (int v = 1; v <= n; v++){
if (!visited[v] && dis[u][v] != INF){
if (minDis[v] > minDis[u] + dis[u][v]){
minDis[v] = minDis[u] + dis[u][v];
pre[v].clear();
pre[v].push_back(u);
}
else if (minDis[v] == minDis[u] + dis[u][v]){
pre[v].push_back(u);
}
}
}
}

dfs(sti["ROM"]);

printf("%d %d %d %d\n%s", ansPathNum, minDis[sti["ROM"]], ansHappinessSum, int(ansHappinessAve), startCity.c_str());
for (int i = path.size() - 2; i >= 0; i--)
printf("->%s", its[path[i]].c_str());

return 0;
}

作者:@臭咸鱼

转载请注明出处:https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!