[PAT A1087]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.
输入格式
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 Klines 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.
输出格式
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.
输入样例
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输出样例
3 3 195 97
HZH->PRS->ROM解析
1.题目大意：模仿旅游，首先给出旅游城市的个数n和边数k，以及起点（起点的快乐值为0）；然后下面n-1行给出除起点以外的城市的名字和快乐值；接下来k行，给出边的端点和长度。要我们输出最短路径，如果有多条最短路径，输出快乐值总和最大的路径，如果连总和都一样，输出平均值最大的路径（注：这里的平均值计算不包含起始点，即如果1是起始点，那么1->2->3->4这条路径计算平均值时不计算1，也就是总和除以3）
2.第一时间发现输入的是字符串，所以需要使用两个数组sti和its完成编号和城市名的匹配。然后就是Djkstra+DFS了
3.这里做题的时候脑子进水了，一开始以为pre[终点]数组的大小就是最短路径条数，其实并不然！
#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
const int maxn = 210;
const int INF = 1000000000;
int n, k;
string st;
int ansHappy = -1, ansHappyAvg = -1; //最大happy总和，最大happy均值
int pathnum = 0; //路径条数
int Graph[maxn][maxn]; //记录图的信息
int d[maxn], happy[maxn];
bool visit[maxn];
vector<int> pre[maxn];
vector<int> tempr, r; //记录当前路径和最终结果
map<string, int> sti; //完成string->int编号的映射
map<int, string> its; //完成int->string的映射
void Dijkstra(int s);
void DFS(int s);
int main()
{fill(Graph[0], Graph[0] + maxn * maxn, INF);cin >> n >> k >> st;sti[st] = 1;its[1] = st;happy[1] = 0;for (int i = 2; i <= n; i++) {string str;int ha;cin >> str >> ha;sti[str] = i;its[i] = str;happy[i] = ha;}for (int i = 1; i <= k; i++) {string s1, s2;int len, id1, id2;cin >> s1 >> s2 >> len;id1 = sti[s1];id2 = sti[s2];Graph[id1][id2] = Graph[id2][id1] = len;}Dijkstra(sti[st]);DFS(sti["ROM"]);printf("%d %d %d %d\n", pathnum, d[sti["ROM"]], ansHappy, ansHappyAvg);for (int i = r.size() - 1; i >= 0; i--) {cout << its[r[i]];if (i != 0) printf("->");}return 0;
}
void DFS(int s) {if (s == sti[st]) {pathnum++;int happysum = 0, cnt = 0;tempr.push_back(s);cnt = tempr.size() - 1;for (int i = tempr.size() - 1; i >= 0; i--) {int id = tempr[i];happysum += happy[id];}if (happysum > ansHappy) {ansHappy = happysum;ansHappyAvg = ansHappy / cnt;r = tempr;}else if (happysum == ansHappy && happysum / cnt > ansHappyAvg) {ansHappyAvg = happysum / cnt;r = tempr;}tempr.pop_back();return;}tempr.push_back(s);for (int i = 0; i < pre[s].size(); i++) DFS(pre[s][i]);tempr.pop_back();
}
void Dijkstra(int s) {fill(d, d + maxn, INF); //设置d数组别忘了~fill(visit, visit + maxn, false); //设置visit数组d[s] = 0;for (int i = 0; i < n; i++) {int u = -1, min = INF;for (int j = 1; j <= n; j++) {if (visit[j] == false && d[j] < min) {u = j;min = d[j];}}if (u == -1) return;visit[u] = true;for (int v = 1; v <= n; v++) {if (visit[v] == false && Graph[u][v] != INF) {if (d[u] + Graph[u][v] < d[v]) {d[v] = d[u] + Graph[u][v];pre[v].clear();pre[v].push_back(u);}else if (d[u] + Graph[u][v] == d[v]) {pre[v].push_back(u);}}}}
}