题目描述

最短路+杂七杂八项
算是PAT 1030的一个变体吧，可以先做那个

算法1

(堆优化Dijkstra) $O(nlogv)$

C++ 代码

#include<iostream>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<string>

using namespace std;
using pii = pair<int, int>;

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<unordered_map<int, int>> g(n);
    vector<int> happy(n);
    vector<string> numCity(n);      //城市名对应的序号的映射
    unordered_map<string, int> cityNum;   //序号对应的城市名
    numCity[0] = s;
    cityNum[s] = 0; 
    for (int i = 1; i < n; ++i) {
        cin >> numCity[i] >> happy[i];
        cityNum[numCity[i]] = i;
    }
    int e = cityNum["ROM"];      //终点序号
    for (int i = 0; i < k; ++i) {
        string s1, s2;
        int cost;
        cin >> s1 >> s2 >> cost;
        g[cityNum[s1]][cityNum[s2]] = g[cityNum[s2]][cityNum[s1]] = cost;   //建无向图
    }
    vector<bool> visit(n, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    vector<int> dis(n, 2e9), col(n, 0);
    vector<int> pre(n, -1);
    pre[0] = 0;
    dis[0] = 0;
    pq.emplace(0, 0);
    vector<int> pathCount(n, 0), NodeCount(n, 0);  //路径数量和节点数量, 注意状态转移, 其他就是常规操作了
    pathCount[0] = 1;          //节点不用算起点
    while (!pq.empty()) {
        auto [y, x] = pq.top(); pq.pop();
        if (visit[x]) continue;
        visit[x] = true;
        for (auto [v, cost] : g[x]) {
            if (visit[v]) continue;
            if (y + cost < dis[v]) {
                dis[v] = y + cost;
                col[v] = happy[v] + col[x];
                pq.emplace(dis[v], v);
                pre[v] = x;
                NodeCount[v] = NodeCount[x] + 1;
                pathCount[v] = pathCount[x];
            } else if (y + cost == dis[v]) {
                pathCount[v] += pathCount[x];
                if (col[x] + happy[v] > col[v] || (col[x] + happy[v] == col[v] && NodeCount[x] + 1 < NodeCount[v])) {
                    col[v] = col[x] + happy[v];
                    NodeCount[v] = NodeCount[x] + 1;
                    pre[v] = x;
                }
            }
        }
    }
    cout << pathCount[e] << " " << dis[e] << " " << col[e] << " " << col[e] / NodeCount[e]  << endl;
    int cur = e;
    vector<int> ans;
    while (cur != 0) {
        ans.push_back(cur);
        cur = pre[cur];
    }
    cout << s;
    for (int i = ans.size() - 1; i >= 0; --i) {
        cout << "->" << numCity[ans[i]];
    }

    return 0;
}