【1087】All Roads Lead to Rome (30 分)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<string>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
dij找出所有最短路径，DFS筛选出同条件下点权之和、平均点权min的路径
注意用map建立城市字符和编号映射
const int MAXV=210;//最大顶点数
const int INF=1000000000;  //无穷大
//n为顶点数，m为边数，st为起点，G为邻接矩阵，weight为点权(幸福值)
//d[]记录最短距离，numPath记录最短路径条数
//maxW记录最大点权之和，maxAvg为最大平均点权
int n,m,st,G[MAXV][MAXV],weight[MAXV];
int d[MAXV],numPath=0,maxW=0;
double maxAvg=0;
bool vis[MAXV]={false}; //vis[i]=true表示顶点i已访问，初始均为false
vector<int> pre[MAXV];//前驱
vector<int> tempPath,path;  //临时路径及最优路径
map<string,int> cityToIndex;  //将城市名转换为编号
map<int,string> indexToCity;  //将编号转换为城市名
void Dijkstra(int s){  //s为起点
  fill(d,d+MAXV,INF);  //初始化起点到每个结点的距离都为无穷大
  d[s]=0; //起点到自己的距离为0
  for(int i=0;i<n;i++){  //循环n次
    int u=-1,MIN=INF; //u使d[u],MIN存放该最小的d[u]
    for(int j=0;j<n;j++){ //找到未访问的顶点中d[]中最小的
      if(vis[j]==false && d[j]<MIN){
        u=j;
        MIN=d[j];
      }
    }
    //找不到小于INF的d[u],说明剩下的顶点和起点s不连通
    if(u==-1)  return;
    vis[u]=true;//标记u为已访问
    for(int v=0;v<n;v++){
      //如果v为访问 && u能够到达v
      if(vis[v] == false && G[u][v] !=INF){
        if(d[u]+G[u][v] < d[v]){ //以u为中介点使d[v]更小
          d[v]=d[u]+G[u][v];  //优化d[v]
          pre[v].clear() ; //清空pre[v]
          pre[v].push_back(u);  //u为v的前驱
        }else if(d[u]+G[u][v] == d[v]){  //找到相同长度的路径
          pre[v].push_back(u); //u为v的前驱之一
        }
      }
    }
  }
}
void DFS(int v){ //v为当前结点
  if(v==st){ //递归边界，到达叶子结点(路径起点)
    tempPath.push_back(v);
    numPath++;  //最短路径条数加1
    int tempW=0; //临时路径tempPath的点权之和
    for(int i=tempPath.size()-2 ; i>=0;i--){ //倒着访问
      int id=tempPath[i]; //当前结点
      tempW +=weight[id];  //增加点id的点券(注意不是i)
    }
    double tempAvg=1.0*tempW / (tempPath.size()-1);  //临时平均点权
    if(tempW >maxW){  //如果当前路径的点权之和更大
      maxW=tempW;  
      maxAvg=tempAvg;  
      path=tempPath;
    }else if(tempW==maxW && tempAvg> maxAvg){
      //点权之和相同，平均点权更大
      maxAvg=tempAvg; 
      path=tempPath;
    }
    tempPath.pop_back();
    return;
  }
  //以下为递归式
  tempPath.push_back(v);//将当前访问结点加入临时路径tempPath的最后面
  for(int i=0;i<pre[v].size();i++){
    DFS(pre[v][i]); //结点v的前驱结点pre[v][i],递归
  }
  tempPath.pop_back(); //遍历完当前所有前驱结点，将当前结点v删除
}
int main(){   
  string start,city1,city2;
  cin >> n >> m >> start; //城市数  路径数  起点
  cityToIndex[start]=0;//将起始城市字符映射成 0
  indexToCity[0]=start; //将0映射成相应的起始城市字符
  for(int i=1;i<=n-1;i++){
    cin >> city1 >> weight[i]; //保存每个城市的幸福值
    cityToIndex[city1]=i;
    indexToCity[i]=city1;
  }
  fill(G[0],G[0]+MAXV*MAXV,INF);  //初始化图G
  for(int i=0;i<m;i++){ 
    cin>>city1>>city2;
    int c1=cityToIndex[city1],c2=cityToIndex[city2]; 
    cin >> G[c1][c2];
    G[c2][c1]=G[c1][c2];
  }
  Dijkstra(0); 
  int rom=cityToIndex["ROM"]; //终点城市字符转换成对应数字
  DFS(rom); //获取最优路径
  printf("%d %d %d %d\n",numPath,d[rom],maxW,(int)maxAvg); //maxW为最大点权之和
  for(int i=path.size()-1;i>=0;i--){  
    cout << indexToCity[path[i]]; //倒着输出路径上的结点
    if(i>0)  cout << "->";
  }
  system("pause"); 
    return 0;   
}