https://www.acwing.com/problem/content/1579/
思路:
最短路里面的经典题型,在最短路的时候维护多个变量。
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
const int N = 250;
unordered_map<string, int> mp; //对字符串离散化
string re_map[N]; //建立一个反映射
int cost[N][N], w[N]; //cost记录花费,w记录达到每个城市可以获得的幸福指数
int pre[N];
int resxingfu[N];
int sum[N];
int d[N];
bool st[N];
int countz[N];
int n, k;
string start,dest;
int cnt = 1;void dijk(int start2)
{memset(d, 0x3f, sizeof d);d[start2] = 0;resxingfu[start2] = 0;sum[start2] = 1;for (int i = 0; i <n; i++){int t = -1;for (int j = 1; j <=n; j++){if (!st[j] && (t == -1 || d[t]>d[j])){t = j;}}st[t] = true;for (int j = 1; j <=n; j++){if (d[j] >d[t] + cost[t][j]){d[j] = d[t] + cost[t][j];pre[j] = t;sum[j] = sum[t];countz[j] = countz[t] + 1;resxingfu[j] = resxingfu[t] + w[j];}else if (d[j] ==d[t] + cost[t][j]){sum[j] += sum[t];if (resxingfu[j] < resxingfu[t] + w[j]){resxingfu[j] = resxingfu[t] + w[j];countz[j]=countz[t] + 1;pre[j] = t;}else if (resxingfu[j] == resxingfu[t] + w[j]){if (countz[j] - 1 > countz[t]){pre[j] = t;countz[j] =countz[t]+1;}}}}}
}int main()
{cin >> n >> k >> start;memset(cost, 0x3f, sizeof cost);dest= "ROM";mp[start] = cnt;re_map[cnt] = start;cnt++;for (int i = 1; i <= n-1; i++){string a;int b;cin >> a >> b;if (!mp.count(a)) mp[a] = cnt, re_map[cnt] = a, cnt++;w[mp[a]] = b;}for (int i = 1; i <= k; i++){string a, b;int spend;cin >> a >> b >> spend;int aa = mp[a], bb = mp[b];cost[aa][bb] = cost[bb][aa] = min(cost[aa][bb],spend);}int start2 = mp[start];int dest2 = mp[dest];dijk(start2);vector<int> res;for (int i = dest2; i != start2; i = pre[i]){res.push_back(i);}res.push_back(start2);cout << sum[dest2] << " " << d[dest2] << " " << resxingfu[dest2] << " " << resxingfu[dest2] / (res.size() - 1) << endl;cout << re_map[res[res.size() - 1]];for (int i = res.size() - 2; i >= 0; i--){cout << "->" << re_map[res[i]];}return 0;
}