1087. All Roads Lead to Rome.md

pat 甲级 1087. All Roads Lead to Rome

题意概述

确实，从我们的城市到罗马有许多不同的旅游路线。你需要以最低的成本找到一条能够获得最大幸福感的路线。

输入输出格式

输入第一行均包含 2 个正整数 N（城市数）和 K（城市对之间的路线总数）；然后是起始城市的名称。接下来的 N-1 行分别给出一个城市的名称和一个整数，代表一个人可以从该城市（起始城市除外）获得的幸福。然后是 K 行，每行以City1 City2 Cost格式描述两个城市之间的路线。这里的城市名称是由 3 个大写英文字母组成的字符串，目的地始终是代表罗马的 ROM。

需要找到成本最低的路线。如果这样的路线不是唯一的，那么需要获得最大的幸福。如果这样的路径仍然不是唯一的，那么我们输出的平均幸福感最大的路线。题目保证这样的解决方案存在并且是唯一的。在输出的第一行中打印 4 个数字：拥有最小成本的路线数量、路线的最小成本、路线的最大幸福度和平均幸福度（仅取整数部分）。然后在下一行中，以City1-> City2-> ...-> ROM格式打印路线。

数据规模

$$2<=N<=200$$

算法设计

题目比较简单，使用 Dijkstra 算法求出符合要求的最短路径，利用 DFS 输出该路径即可，具体实现可见代码。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 505;
using agg2 = array<gg, 2>;
struct Edge {
    gg to, cost;
    Edge(gg t, gg c) : to(t), cost(c) {}
};
vector<vector<Edge>> graph(MAX);
vector<gg> dis(MAX, INT_MAX), city(MAX), past(MAX, -1), pastNum(MAX),
    pathNum(MAX), happy(MAX);
void Dijkstra(gg s) {
    priority_queue<agg2, vector<agg2>, greater<agg2>> pq;
    pastNum[s] = dis[s] = 0;
    pathNum[s] = 1;
    pq.push({0, s});
    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        if (dis[p[1]] != p[0]) {
            continue;
        }
        for (auto& e : graph[p[1]]) {
            if (dis[e.to] > p[0] + e.cost) {
                dis[e.to] = p[0] + e.cost;
                past[e.to] = p[1];
                pastNum[e.to] = pastNum[p[1]] + 1;
                pathNum[e.to] = pathNum[p[1]];
                happy[e.to] = happy[p[1]] + city[e.to];
                pq.push({dis[e.to], e.to});
            } else if (dis[e.to] == p[0] + e.cost) {
                pathNum[e.to] += pathNum[p[1]];
                if (make_tuple(happy[e.to], pastNum[p[1]] + 1) <
                    make_tuple(happy[p[1]] + city[e.to], pastNum[e.to])) {
                    past[e.to] = p[1];
                    pastNum[e.to] = pastNum[p[1]] + 1;
                    happy[e.to] = happy[p[1]] + city[e.to];
                }
            }
        }
    }
}
void dfs(gg v, vector<string>& vs) {
    if (past[v] == -1) {
        cout << vs[v];
        return;
    }
    dfs(past[v], vs);
    cout << "->" << vs[v];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ki;
    cin >> ni >> ki;
    vector<string> vs(ni);
    unordered_map<string, gg> um;
    cin >> vs[0];
    um[vs[0]] = 0;
    for (gg i = 1; i < ni; ++i) {
        cin >> vs[i] >> city[i];
        um[vs[i]] = i;
    }
    for (gg i = 0; i < ki; ++i) {
        string a, b;
        gg c;
        cin >> a >> b >> c;
        graph[um[a]].push_back(Edge(um[b], c));
        graph[um[b]].push_back(Edge(um[a], c));
    }
    Dijkstra(0);
    gg d = um["ROM"];
    cout << pathNum[d] << " " << dis[d] << " " << happy[d] << " "
         << happy[d] / pastNum[d] << "\n";
    dfs(d, vs);
    return 0;
}