1087 All Roads Lead to Rome
Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers N (2≤N≤200), the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N−1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format City1 City2 Cost. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.
Output Specification:
For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommanded. If such a route is still not unique, then we output the one with the maximum average happiness – it is guaranteed by the judge that such a solution exists and is unique.
Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommanded route. Then in the next line, you are supposed to print the route in the format City1->City2->...->ROM.
Sample Input:
6 7 HZH ROM 100 PKN 40 GDN 55 PRS 95 BLN 80 ROM GDN 1 BLN ROM 1 HZH PKN 1 PRS ROM 2 BLN HZH 2 PKN GDN 1 HZH PRS 1
Sample Output:
3 3 195 97 HZH->PRS->ROM
题意
从我们的城市到达罗马有许多不同的旅游路线。
请你在成本最低的旅游路线之中，找到使得游客获得最大幸福感的路线。如果该路线不唯一，则找到最大平均幸福感的路线，其中平均幸福感是不包括起点的。
第一行输入分别为城市数量 N NN ，路线数量 K KK ，以及起点。
接下来的 N − 1 N-1N−1 行输入每个城市的幸福感值。
接下来的 K KK 行则输入每条路的信息。
第一行输出四个整数，最小成本的路线数量，最小成本，幸福感，平均幸福感（只取整数部分）。
第二行，按照 City1->City2->...->ROM 的格式输出路线。
思路
这道题同样可以利用迪杰斯特拉算法去找最优解，具体思路如下：
1.先对所有城市进行映射，因为给定的城市名字为字符串类型，需要映射成整数，可以用一个哈希表 mp 存储每个城市映射后的下标。
2.输入每条路的信息，注意这里需要用到上面映射后的下标进行存储，之后的迪杰斯特拉同理。
3.在进行迪杰斯特拉算法的过程中，不断更新答案，找到最优路线。首先要去判断当前路径花费是否最小，如果存在另一条花费相等的路径则要进一步判断该路径获得的幸福感是否最大，如果还是出现相等的路径则再进一步判断该路径的结点数量是否最小，然后进行对应的更新操作。
4.输出最终结果，注意需要先将 pre 中的路线全部存到一个容器中再逆向输出。
代码
#include<bits/stdc++.h> using namespace std; const int N = 210; int n, k; //最小花费、最小花费路径数量、幸福感值、最小点数、最短路径的前一个点 int dist[N], cnt[N], hp[N], sum[N], pre[N]; int d[N][N], w[N]; bool st[N]; string city[N]; unordered_map<string, int> mp; //迪杰斯特拉算法 void dijkstra() { //初始化 memset(dist, 0x3f, sizeof dist); dist[1] = 0, cnt[1] = 1; for (int i = 0; i < n; i++) { int t = -1; for (int j = 1; j <= n; j++) //找到最短边权 if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; for (int j = 1; j <= n; j++) //更新信息 if (dist[j] > dist[t] + d[t][j]) //如果最小花费可以更新 { dist[j] = dist[t] + d[t][j]; cnt[j] = cnt[t]; hp[j] = hp[t] + w[j]; sum[j] = sum[t] + 1; pre[j] = t; } else if (dist[j] == dist[t] + d[t][j]) //如果最小花费相等 { cnt[j] += cnt[t]; if (hp[j] < hp[t] + w[j]) //如果幸福感可以更新 { hp[j] = hp[t] + w[j]; sum[j] = sum[t] + 1; pre[j] = t; } else if (hp[j] == hp[t] + w[j]) //如果幸福感也相等 { if (sum[j] > sum[t] + 1) //如果存在点数更小的路径 { sum[j] = sum[t] + 1; pre[j] = t; } } } } } int main() { cin >> n >> k >> city[1]; mp[city[1]] = 1; //对所有城市进行映射 for (int i = 2; i <= n; i++) { cin >> city[i] >> w[i]; mp[city[i]] = i; } //输入所有边的信息 memset(d, 0x3f, sizeof d); for (int i = 0; i < k; i++) { string a, b; int x, y, c; cin >> a >> b >> c; x = mp[a], y = mp[b]; d[x][y] = d[y][x] = min(d[x][y], c); } dijkstra(); //寻找满足要求的路径 //输出结果 int T = mp["ROM"]; cout << cnt[T] << " " << dist[T] << " " << hp[T] << " " << hp[T] / sum[T] << endl; vector<int> path; for (int i = T; i != 1; i = pre[i]) path.push_back(i); cout << city[1]; for (int i = path.size() - 1; i >= 0; i--) cout << "->" << city[path[i]]; cout << endl; return 0; }
