题意：

有N个城市，M条无向边，从某个给定的起始城市出发，前往名为ROM的城市。每个城市（除了起始城市）都有一个点权（称为幸福值），和边权（每条边所需的花费）。求从起点到ROM所需要的最少花费，并输出其路径。如果路径有多条，给出幸福值最大的那条。如果仍然不唯一，选择路径上的城市平均幸福值最大的那条路径。

思路:

这种题，如果简单一点，要求没那么多的情况，可以直接在dijkstra中写用dp的思想顺便求出幸福值最大的情况，但是这题还有平均幸福值，所以只能先用dijkstra求出最小花费的所有路径，再利用dfs回溯进行求解。

#include
    
     #define inf 0x3f3f3f3fusing namespace std;const int maxn=250;int road[maxn][maxn];int cost[maxn];int dis[maxn];bool vis[maxn];int n,m;map
     
       m1;map
      
        m2;vector
       
         pre[maxn];vector
        
          temppath,path;int maxhap,pathnum;double avghap;void dijkstra(int start){    fill(dis,dis+maxn,inf);    fill(vis,vis+maxn,false);    dis[start]=0;    for(int i=0;i
         
          dis[u]+road[u][v]){ dis[v]=dis[u]+road[u][v]; pre[v].clear(); pre[v].push_back(u); }else if(dis[v]==dis[u]+road[u][v]){ pre[v].push_back(u); } } } }}void dfs(int v){ temppath.push_back(v); if(v==1){ int sum=0; for(int i=0;i
          
           maxhap){ maxhap=sum; path=temppath; avghap=avg; }else if(sum==maxhap&&avg>avghap){ avghap=avg; path=temppath; } pathnum++; return; } for(int i=0;i
           
            >n>>m>>start; m1[start]=1; m2[1]=start; for(int i=1;i
            
             >temp>>cost[i+1]; m1[temp]=i+1; m2[i+1]=temp; } fill(road[0],road[0]+maxn*maxn,inf); string sa,sb; int d; for(int i=0;i
             
              >sa>>sb>>d; road[m1[sa]][m1[sb]]=d; road[m1[sb]][m1[sa]]=d; } dijkstra(1); dfs(m1["ROM"]); printf("%d %d %d %d\n", pathnum, dis[m1["ROM"]], maxhap, (int)avghap); for (int i = path.size() - 1; i >= 1; i--) { cout << m2[path[i]] << "->"; } cout << "ROM" << endl; return 0;}