A1087
Description：
从我们的城市到罗马有许多条路，求一条花费最小且获得最多快乐的路径。
Input：
- 每个测试点一个样例；
- 首行有两个正整数：城市数N[2,200]，两城市间的路径最条数K，然后是起点的城市名；
- 接下来N-1行给出了城市名和可以从这个城市获得的幸福值，除了最开始的城市；
- 接下来K行每行描述了连接两个城市的道路及其花费，城市名是三个大写英语字母，终点是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
Output：
- 求最低花费的路，如果不唯一，输出最大幸福值的路，如果仍不唯一，输出具有最大平均幸福值的路线；
- 首行输出四个数字，具有最小花销的不同路线数（Dijkstra + DFS）、所用花销、幸福值以及推荐路线的平均幸福值(去尾法保留正数)；
- 接下来输出城市路线；
3 3 195 97 HZH->PRS->ROM
算法描述：
- Dijkstra得出最小cost值，DFS得到所有cost值为最小值的路径，并同时统计happyness值；
- 写题速度还是太慢了，因为代码行数原因吗
- 有关Dijkstra小根堆优化及邻接表详细背诵模板请移步A1003 Emergency
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 205;
const int maxm = (maxn*maxn)/2;
const int inf = 0x3f3f3f3f;
typedef pair<int, int>PII;struct edge{int cost;int v;int next;
}e[maxm];
struct ans{int hpy;int averhpy;vector<int>route;
};
string start;
int p[maxn], eid, n, k, happy[maxn], dis[maxn];
map<string,int>m;
map<int, string>tostr;
int indexcnt = 2;
set<PII, less<PII>>minheap;
vector<ans>ansv;
bool vis[maxn];
bool cmp(ans a, ans b){if(a.hpy != b.hpy) return a.hpy > b.hpy;return a.averhpy > b.averhpy;
}
void init(){memset(p, -1, sizeof(p));memset(vis, 0, sizeof(vis));memset(dis, 0x3f, sizeof(dis));memset(happy, 0, sizeof(happy));eid = 0;
}
void ins(int u, int v, int co){e[eid].v = v;e[eid].cost = co;e[eid].next = p[u];p[u] = eid++;
}
void in(int u, int v, int co){ins(u, v, co);ins(v, u, co);
}
int getIndex(string str){if(str == start){m.insert(make_pair(start, 1));tostr.insert(make_pair(1, start));return 1;}if(str == "ROM"){m.insert(make_pair(str, n));tostr.insert(make_pair(n, str));return n;}if(m.count(str) == 0){m.insert(make_pair(str, indexcnt));tostr.insert(make_pair(indexcnt, str));return indexcnt++;}else return m[str];
}
bool dijkstra(){minheap.insert(PII(0, 1));dis[1] = 0;for(int i = 1; i <= n; i++){if(minheap.size() == 0) return false;auto it = minheap.begin();int u = it->second;minheap.erase(*it);vis[u] = true;for(int x = p[u]; x != -1; x = e[x].next){int v = e[x].v;if(!vis[v] && dis[u]+e[x].cost < dis[v]){minheap.erase(PII(dis[v], v));dis[v] = dis[u] + e[x].cost;minheap.insert(PII(dis[v], v));}}}return true;
}
int happycnt = 0, costcnt = 0;
vector<int>record;
void dfs(int now, int pre){if(now == n && costcnt == dis[n]){ans a;a.hpy = happycnt;a.averhpy = happycnt / record.size();a.route = record;ansv.push_back(a);return ;}for(int v = p[now]; v != -1; v = e[v].next){if(costcnt+e[v].cost<=dis[n] && e[v].v != pre){record.push_back(e[v].v);happycnt += happy[e[v].v];costcnt += e[v].cost;dfs(e[v].v, now);costcnt -= e[v].cost;happycnt -= happy[e[v].v];record.pop_back();}}
}
int main()
{
#ifdef ONLINE_JUDGE
#elsefreopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGEinit();cin>>n>>k>>start;getIndex(start);string c1, c2;int tcost;for(int i = 0; i < n-1; i++){cin>>c1>>tcost;happy[getIndex(c1)] = tcost;}for(int i = 0; i < k; i++){cin>>c1>>c2>>tcost;in(m[c1], m[c2], tcost);}dijkstra();dfs(1, -1);sort(ansv.begin(), ansv.end(), cmp);printf("%d %d %d %d\n", ansv.size(), dis[n], ansv[0].hpy, ansv[0].averhpy);cout<<tostr[1];for(int i = 0; i < ansv[0].route.size(); i++){cout<<"->"<<tostr[ansv[0].route[i]];}cout<<endl;return 0;
}