PAT甲级1087All Roads Lead to Rome

Posted on | | Visitors:
Words count in article: 758 字 | Reading time ≈ 4 分

题目链接

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/

欢迎讨论和交流!