题意： 有N个城市，M条无向边，从某个给定的起始城市出发，前往名为ROM的城市。每个城市（除了起始城市）都有一个点权（称为幸福值），和边权（每条边所需的花费）。求从起点到ROM所需要的最少花费，并输出其路径。如果路径有多条，给出幸福值最大的那条。如果仍然不唯一，选择路径上的城市平均幸福值最大的那条路径
tip:深搜+剪枝+map映射+状态记录
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int happiness[203],m[203][203]= {0};
int checked[203]= {0};
int minlen=1e7,maxhapp=0,sum=0;
double maxavl=0;
int n,k,e;
vector<int> ans,temp;
void dfs(int s,int len,int happ,int count) {
temp.push_back(s);
checked[s]=1;
if(len>minlen)//剪枝
return ;
if(s==e) {
if(len==minlen) {
sum++;
if(happ<maxhapp)
return ;
if(happ==maxhapp) {//开心值一样时，找最大平均开心值
if(maxavl<1.*happ/(count-1)) {
maxavl=1.*happ/(count-1);
ans=temp;
}
} else {//更新最大开心值
maxhapp=happ;
maxavl=1.*happ/(count-1);
ans=temp;
}
} else if(len<minlen) {//更新最小费用
minlen=len;
maxhapp=happ;
maxavl=1.*happ/(count-1);
ans=temp;
sum=1;
}
return ;
}
for(int i=0; i<n; ++i)
if(m[s][i]&&!checked[i]) {
dfs(i,len+m[s][i],happ+happiness[i],count+1);
checked[i]=0;
temp.pop_back();
}
}
int main() {
string s;
cin>>n>>k>>s;
map<string,int> m1;
map<int ,string>m2;
for(int i=0; i<n-1; ++i) {
string name;
int happ;
cin>>name>>happ;
m1[name]=i;//城市名映射到编号
m2[i]=name;//编号映射到城市名
happiness[i]=happ;//每座城市的开心值
}
e=m1["ROM"];
m1[s]=n-1;
m2[n-1]=s;
happiness[n-1]=0;
for(int i=0; i<k; ++i) {
string a,b;
int len;
cin>>a>>b>>len;
m[m1[a]][m1[b]]=len;
m[m1[b]][m1[a]]=len;
}
dfs(m1[s],0,0,1);
cout<<sum<<" "<<minlen<<" "<<maxhapp<<" ";
printf("%.0lf\n",maxavl);
cout<<s;
for(int i=1; i<ans.size(); ++i)
cout<<"->"<<m2[ans[i]];
return 0;
}