PAT甲级1087. All Roads Lead to Rome
题意：
确实有从我们这个城市到罗马的不同的旅游线路。您应该以最低的成本找到您的客户的路线，同时获得最大的幸福。
输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行包含2个正整数N（2 <= N <= 200），城市数，K，
双城之间的路线总数;其次是起始城市的名称。下一个N-1行每个都给出一个城市的名字和一个整数，代表从城市可以获得的幸福，除了起始城市。然后K行跟随，每个描述两个城市之间的路线，格式为“City1 City2 Cost”。
这里一个城市的名字是3个英文字母，目的地总是ROM代表罗马。
输出规格：
对于每个测试用例，我们应该以最低的成本找到路由。如果这样一条路线不是独一无二的，那么最好是幸福的路线。如果这样的路线还不是唯一的，
那么我们输出一个具有最大平均幸福感的人 - 法官保证这样的解决方案存在并且是独一无二的。
因此，在第一行输出中，您必须打印4个数字：成本最低，成本，幸福的不同路线的数量，
和推荐路线的平均幸福（仅占整数部分）。然后在下一行，您应该以“City1-> City-> ...-> ROM”的格式打印路线。
思路：
Dijkstra找出最短路径，dfs遍历找到所有的路线，根据题意找出recommend的路线。 题意要看清呀。
这个我还以为是有包含最大的happiness的city的路线。= =。捉急。。其实是总和的happiness的最大就ok了。
ac代码：
C++
// pat1087.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<stdio.h>
#include<map>
#include<cmath>
#include<unordered_map>
#include<unordered_set>
using namespace std;
const int INF = 0x7fffffff;
int n, k;
string starting;
unordered_map<string, int> citytoi;
unordered_map<int,string> itocity;
unordered_map<int, int> happiness;
int mymap[201][201];
int Dijkstra()
{
vector<int> len(n, INF);
vector<int> visit(n, 0);
len[0] = 0;
int now, minlen;
while (1)
{
now = -1;
minlen = INF;
for (int i = 0; i < n; i++)
{
if (!visit[i] && len[i] < minlen)
{
minlen = len[i];
now = i;
}
}
if (now == -1 || now == citytoi["ROM"]) break;
visit[now] = 1;
for (int i = 0; i < n; i++)
{
if (!visit[i] && mymap[now][i] && mymap[now][i] + minlen < len[i])
{
len[i] = mymap[now][i] + minlen;
}
}
}
return len[citytoi["ROM"]];
}
vector<vector<int> >res;
void dfs(vector<int> temp, int count, int need, int now,vector<int>& visit)
{
visit[now] = 1;
if (count > need) return;
if (count == need && now == citytoi["ROM"])
{
int maxhapp = happiness[temp[0]];
int len = temp.size();
int sum = 0;
for (int i = 0; i < len; i++)
{
maxhapp = max(maxhapp, happiness[temp[i]]);
sum += happiness[temp[i]];
}
temp.insert(temp.begin(), sum / len); //1 avg
temp.insert(temp.begin(), sum); //0 sum
res.push_back(temp);
return;
}
for (int i = 0; i < n; i++)
{
if (!visit[i] && mymap[now][i])
{
temp.push_back(i);
dfs(temp, count + mymap[now][i], need, i, visit);
visit[i] = 0;
temp.pop_back();
}
}
}
bool cmp(vector<int>& a, vector<int>& b)
{
if (a[0] != b[0]) return a[0] > b[0];
else return a[1] > b[1];
}
int main()
{
scanf("%d %d", &n, &k);
cin >> starting;
//input happiness
citytoi[starting] = 0;
itocity[0] = starting;
happiness[0] = 0;
char city1[4],city2[4];
string c1, c2;
int num;
for (int i = 1; i <= n - 1; i++)
{
scanf("%s %d", city1, &num);
c1 = string(city1);
citytoi[c1] = i;
itocity[i] = c1;
happiness[i] = num;
}
//input route
int ic1, ic2;
for (int i = 0; i < k; i++)
{
scanf("%s %s %d", city1, city2, &num);
c1 = string(city1), c2 = string(city2);
ic1 = citytoi[c1], ic2 = citytoi[c2];
mymap[ic1][ic2] = mymap[ic2][ic1] = num;
}
//caculate
int need = Dijkstra();
vector<int> temp;
vector<int> dfsvisit(n, 0);
dfs(temp, 0, need, 0, dfsvisit);
//output
sort(res.begin(), res.end(), cmp);
printf("%d %d %d %d\n",res.size(), need, res[0][0], res[0][1]);
cout << starting << "->";
int len = res[0].size();
for (int i = 2; i < len - 1; i++)
{
cout << itocity[res[0][i]] << "->";
}
cout << itocity[res[0][len - 1]] << endl;
return 0;
}