题意：从起点到ROM点的最短路径有几条，最短路的长度是多少，happiness，平均的happiness,以及路径。输出的路径是先满足最短路，再满足最大happiness，再满足最大平均happiness。
思路：
大体的思路就是将从起点到终点的最短路径都找出来，并维护好相关信息，然后放入优先队列中，输出队首的元素。
太久不写代码，差点写到自闭。代码出错时首先要回去看看题意，确认题意和自己写的一致。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<vector>
#define mod (1000000007)
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
struct node{int u,v,w,nxt;
}side[80000];
map<string,int> mp;
map<int,string> imp;
int head[1000],cnt=0,hap[1000];
void add(int u,int v,int w){side[cnt].u=u;side[cnt].v=v;side[cnt].w=w;side[cnt].nxt=head[u];head[u]=cnt++;
}
struct nod{int v,w;int hap,num;string s;nod(){}nod(int vv,int ww,int h,int nn,string ss){v=vv;w=ww;hap=h;num=nn;s=ss;}friend bool operator<(nod a,nod b){if(a.w==b.w){if(a.hap==b.hap){if(a.num==b.num){return a.s<b.s;}return a.num>b.num;}return a.hap<b.hap;}return a.w>b.w;}
};
int dis[1000];
string s,s2,st;
set<nod> S[220];
priority_queue<nod> qq;
void bfs(int ed){for(int i=0;i<500;i++) dis[i]=9999999;priority_queue<nod> que;que.push(nod(mp[st],0,0,0,st));while(!que.empty()){nod nn=que.top();que.pop();if(nn.v==ed){qq.push(nn);continue;} for(int i=head[nn.v];i!=-1;i=side[i].nxt){int ty=side[i].v;if(nn.w+side[i].w<dis[ty]){S[ty].clear();dis[ty]=nn.w+side[i].w;S[ty].insert(nod(ty,dis[ty],nn.hap+hap[ty],nn.num+1,nn.s+"->"+imp[ty]));que.push(nod(ty,dis[ty],nn.hap+hap[ty],nn.num+1,nn.s+"->"+imp[ty]));}else if(nn.w+side[i].w==dis[ty]){S[ty].insert(nod(ty,dis[ty],nn.hap+hap[ty],nn.num+1,nn.s+"->"+imp[ty]));que.push(nod(ty,dis[ty],nn.hap+hap[ty],nn.num+1,nn.s+"->"+imp[ty]));}}}
}
int idx=1;
int main(){memset(head,-1,sizeof(head));int n,k,ha;cin>>n>>k>>st;mp[st]=idx++;imp[1]=s;for(int i=1;i<n;i++){cin>>s>>ha;if(mp[s]==0)mp[s]=idx++;imp[idx-1]=s;hap[mp[s]]=ha;}int ed=mp["ROM"];for(int i=0;i<k;i++){cin>>s>>s2>>ha;add(mp[s],mp[s2],ha);add(mp[s2],mp[s],ha);}bfs(ed);nod nn=qq.top();printf("%d %d %d %d\n",S[ed].size(),nn.w,nn.hap,nn.hap/nn.num);cout<<nn.s<<endl;return 0;
}