C++ 代码

#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 200;
const int INF = 1e6;
unordered_map<string, int> s2n;
unordered_map<int, string> n2s;
int g[N][N], dis[N], vis[N], hap[N], col[N], pre[N];
int n, k, pathCount[N], nodeCount[N];
string starting;

void dijkstra() {
    fill(dis, dis + N, INF);
    dis[0] = 0;
    col[0] = 0;
    nodeCount[0] = 0;
    pathCount[0] = 1;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++)
            if (!vis[j] && dis[j] < MIN) {
                MIN = dis[j];
                u = j;
            }
        vis[u] = 1;
        for (int v = 0; v < n; v++) {
            if (!vis[v]) {
                if (dis[u] + g[u][v] < dis[v]) { // 最短路径
                    dis[v] = dis[u] + g[u][v];
                    col[v] = col[u] + hap[v];
                    nodeCount[v] = nodeCount[u] + 1;
                    pathCount[v] = pathCount[u];
                    pre[v] = u;
                } else if (dis[u] + g[u][v] == dis[v]) { 
                    pathCount[v] += pathCount[u];
                    if (col[u] + hap[v] > col[v]) { // 最大幸福感
                        col[v] = col[u] + hap[v];
                        nodeCount[v] = nodeCount[u] + 1;
                        pre[v] = u;
                    } else if (col[u] + hap[v] == col[v]) { 
                        if (nodeCount[u] + 1 < nodeCount[v]) { // 最大平均幸福感，即最少结点数
                            nodeCount[v] = nodeCount[u] + 1;
                            pre[v] = u;
                        }
                    }
                }
            }
        }
    }
}

void dfs(int x) {
    if (x == 0)
        cout << starting;
    else {
        dfs(pre[x]);
        cout << "->" << n2s[x];
    }
}

int main() {
    cin >> n >> k >> starting;
    s2n[starting] = 0, n2s[0] = starting;
    for (int i = 1; i < n; i++) {
        cin >> n2s[i] >> hap[i];
        s2n[n2s[i]] = i;
    }
    fill(g[0], g[0] + N * N, INF);
    while (k--) {
        string u, v;
        int w;
        cin >> u >> v >> w;
        g[s2n[u]][s2n[v]] = g[s2n[v]][s2n[u]] = w;
    }
    dijkstra();
    cout << pathCount[s2n["ROM"]] << " " << dis[s2n["ROM"]] << " "
         << col[s2n["ROM"]] << " " << col[s2n["ROM"]] / nodeCount[s2n["ROM"]] << endl;
    dfs(s2n["ROM"]);
    return 0;
}