这道题其实就是一道最短路水题，spfa+dfs+hash，但是写代码和调试花的时间都有点长，记录一下细节，警告自己下次要更加耐心。
- 这道题的地区名字都是字符串，所以可以用map存储字符串和int的对应关系。由于本题既需要通过string寻找int，也需要通过int寻找string，因此我建立了两个map来进行这一操作。
- 当dfs的时候，我找到路径后直接返回了，但是忘记了把最后一个元素清除，因此一开始一直得出错误的结论。
- 一开始我在spfa里进行判断快乐值和最短路径，在dfs里判断平均快乐值，后来改为了在dfs里判断快乐值和平均快乐值，只在spfa里判断最短路径，这样对于我来说，思路和代码更加清晰。
- 一开始读题，居然没发现还要求最短路径数目，慌了一瞬间，还好不难求。以后要读题的时候更加细心。
- 一开始没有注意，起点是没有快乐值的，而且循环输入快乐值的时候，输入的是n-1个数，不是n个数，我没注意这一点，调试了半天才发现。
#include <iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstdlib>
#include<queue>
#include<cstring>
#include<set>
using namespace std;
int n,m;
int c[520];
int in[520]={0};//节点是否在队列中
int dis[520];
int cost[520];
queue<int>q;
set<int>pre[520];//每个节点的前驱节点
struct Node
{int v;int w;int u;int cost;Node(int _u,int _v,int _w):u(_u),v(_v),w(_w){}
};
int s;
map<string,int>dic;
map<int,string>dic2;
vector<Node>a[520];
vector<Node>b[520];
int happy[520];
int happyDis[520];
string start;
vector<int>ans;
vector<int>tempAns;
int count1=0x3f3f3f3f;
int tempCount=0;
int total=0;
int happyAns=0;
void dfs(int cur)
{tempAns.push_back(cur);tempCount++;if(cur==s){total++;/*cout<<"cur:"<<cur<<endl;cout<<"total:"<<total<<endl;cout<<"tempCount:"<<tempCount<<endl;cout<<"size:"<<tempAns.size()<<endl;total++;cout<<"当前路径："<<endl;for(int i=tempAns.size()-1;i>=1;i--){string tempStr=dic2.find(tempAns[i])->second;cout<<tempStr<<"->";}cout<<"ROM"<<endl;*/int maxHappy=0;for(int i=0;i<tempAns.size();i++){maxHappy+=happy[tempAns[i]];}// cout<<"maxHappy:"<<maxHappy<<endl;if(maxHappy>happyAns){// cout<<"maxHappy更大"<<endl;happyAns=maxHappy;ans=tempAns;count1=tempCount;tempAns.pop_back();tempCount--;return;}else if(maxHappy==happyAns){if(tempCount<count1){count1=tempCount;ans=tempAns;}tempAns.pop_back();tempCount--;return;}}for(int i=0;i<b[cur].size();i++){int u=b[cur][i].u;int w=b[cur][i].w;// if(dic2.find(cur)->second=="PRS")// cout<<"cur:"<<dic2.find(cur)->second<<" "<<"u:"<<dic2.find(u)->second<<endl;if(dis[cur]==dis[u]+w){if(dic2.find(cur)->second=="PRS"){//cout<<"当u:"<<dic2.find(u)->second<<"的时候，合格"<<endl;}dfs(u);}}tempAns.pop_back();tempCount--;}
int main()
{char temp[50];scanf("%d%d%s",&n,&m,temp);start=temp;dic.insert(pair<string,int>(start,1));dic2.insert(pair<int,string>(1,start));happy[1]=0;fill(dis,dis+n+10,0x3f3f3f3f);fill(happyDis,happyDis+n+10,0);for(int i=2;i<=n;i++){char temp1[50];int x;scanf("%s%d",temp1,&x);string temp2=temp1;dic.insert(pair<string,int>(temp2,i));dic2.insert(pair<int,string>(i,temp2));happy[i]=x;}for(int i=1;i<=m;i++){char temp1[50],temp2[50];int z;scanf("%s%s%d",temp1,temp2,&z);string temp3,temp4;temp3=temp1;temp4=temp2;int x=dic.find(temp3)->second;int y=dic.find(temp4)->second;a[x].push_back(Node(x,y,z));a[y].push_back(Node(y,x,z));b[x].push_back(Node(y,x,z));b[y].push_back(Node(x,y,z));}s=dic.find(start)->second;in[s]=1;q.push(s);dis[s]=0;happyDis[s]=happy[s];while(!q.empty()){int head=q.front();q.pop();in[head]=0;for(int i=0;i<a[head].size();i++){int v=a[head][i].v;int w=a[head][i].w;if(dis[v]>dis[head]+w){dis[v]=dis[head]+w;happyDis[v]=happyDis[head]+happy[v];if(!in[v]){in[v]=1;q.push(v);}}}}int t=dic.find("ROM")->second;dfs(t);count1--;cout<<total<<" "<<dis[t]<<" "<<happyAns<<" "<<happyAns/count1<<endl;for(int i=ans.size()-1;i>=1;i--){string tempStr=dic2.find(ans[i])->second;cout<<tempStr<<"->";}cout<<"ROM";}