PAT (Advanced Level) Practice 1087 All Roads Lead to Rome (30 分) 凌宸1642

题目描述：

Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.

译：实际上从我们的城市去罗马有很多不同的旅游路线。你应该喂你的顾客找出花费最小并且获得开心值最大的路线！

---

Input Specification (输入说明):

Each input file contains one test case. For each case, the first line contains 2 positive integers N (2≤N≤200), the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N−1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format City1 City2 Cost. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome..

译：每个输入文件包含一个测试用例。对于每个用例，第一行中包含两个正整数， 城市总数 N (2≤N≤200) ，和城市之间能直接到达的路径总数 K ；紧跟着是起点城市的名称。接下来 N - 1行，每行给处一个城市的名称和一个代表可以从该城市获得的开心值的整数，除起点城市外。接下来K行，每行给处形式如City1 City2 Cost的关于两个城市之间的路径的描述。所有的城市名称都是有三个大写英文字母组成，并且目的地固定为ROM 表示罗马城。

---

output Specification (输出说明):

For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommanded. If such a route is still not unique, then we output the one with the maximum average happiness -- it is guaranteed by the judge that such a solution exists and is unique.

Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommanded route. Then in the next line, you are supposed to print the route in the format City1->City2->...->ROM..

译：对于每个测试用例，我们应该找出花费最小的路径。如果这样的路径不唯一，那就选择获得开心值最大的路径。如果这样的路径依旧不唯一，我们应该输出平均开心值最大的路径——题目保证这样的路径存在并且唯一。

因此第一行需要输出四个数字：花费最小的路径数，最小花费，获得的最大开心值，最大平均开心值(只取整数部分)。第二行，你应该用此格式 City1->City2->...->ROM输出该条路径。

---

Sample Input (样例输入):

6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1

---

Sample Output (样例输出):

3 3 195 97
HZH->PRS->ROM

---

The Idea：

首先很明显这是一题单源最短路径的问题。并且有三个维度，花费最小，最大开心值，平均最大开心值。

• 第一步，建图，由于城市的名称都是三位的大写英文字母，所以可以建立城市名称 name 和数字编号之间的映射，方便后续操作 。
• 第二步，理解题意中，花费其实就是城市之间距离，平均最大开心值，就是经过的城市最少。
• 第三步，选择 Dijkstra 算法进行求解，具体可见代码的注释。
• 第四步，按要求输出。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 210 ;
const int inf = 0x3fffffff ;
int n , k , cost , rom ; 
string st , tem , tem1 ;
int happy[maxn] ;			// 各点的 happy 值  
int rnum[maxn] ;			// 起点到各点的最短路径数 
int d[maxn] ;				// 起点到各点的最短路径 
int pre[maxn] ;				// 起点到各点的最短且最大 happy 值路径上的前驱结点 
int happpMax[maxn] ;		// 起点到各点的最大 happy 值 
int g[maxn][maxn] ;    	   	// 表示图的二维矩阵 
int pass[maxn] ;			// 起点到各点的最短且最大 happy 值路径上最少经过几个点 
bool vis[maxn] ;       	   	// 标记顶点是否已经被访问 
map<string , int > si ;		// 城市名 到 数字 的映射
map<int , string > is ;		// 数字 到 城市名 的映射
vector<int> ansRoute ;		// 记录路径
void dijkstra(int s){
	fill(d , d + maxn , inf) ;
	fill(pre , pre + maxn , -1) ; 
	d[s] = 0 ; 			// 起点到自身的最短路径为 0 
	rnum[s] = 1 ; 		// 起点到自身的最短路径数为 1 
	pass[s] = 0 ; 		// 起点到自身的经过点数为 0 
	pre[0] = 0 ;
	for(int i = 0 ; i < n ; i ++){
		int u = - 1 , minv = inf ;
		for(int j = 0 ; j < n ; j ++){
			if(vis[j] == false && d[j] < minv ){
				u = j ;
				minv = d[j] ;
			}
		}
		if(u == -1) return ; 	// 没有找到当前最短的路径，说明剩下的点与当前点不连通，直接返回
		vis[u] = true ;			// 标记当前结点已访问
		for(int v = 0 ; v < n ; v ++){
			if(vis[v] == false && g[u][v] != inf){ 		// 如果存在 u-->v 的路径，并且 v 还未被访问
				if(d[u] + g[u][v] < d[v]){ 					// 如果选择 u-->v 的路径 ，能让起点到 v 的距离减小，则更新
					d[v] = d[u] + g[u][v] ;					// 更新 d[v]
					rnum[v] = rnum[u] ;						// 起点到点 v 的最短路径数，等于起点到点 u 的最短路径数
					happpMax[v] = happpMax[u] + happy[v] ; 	// 起点到点 v 的最大开心值，等于起点到点 u 的最大开心值 + 城市 v 的开心值
					pass[v] = pass[u] + 1 ; 				// 起点到点 v 经过的城市数，等于起点到点 u 经过的城市数 + 1
					pre[v] = u ; 							// v 的先驱结点为 u
				}else if(d[u] + g[u][v] == d[v]){			// 如果选择 u-->v 的路径的最短路径长度 等于 起点到 v 的最短路径长度
					rnum[v] += rnum[u] ;		// 起点到点 v 的最短路径数，等于起点到点 u 的最短路径数 + 原有的起点到点 v 的最短路径数
					if(happpMax[u] + happy[v] > happpMax[v]){ // 如果选择 u-->v 的路径 ，能获得更大的开心值
						happpMax[v] = happpMax[u] + happy[v] ; // 更新 happpMax[v]
						pass[v] = pass[u] + 1 ;					// 起点到点 v 经过的城市数，等于起点到点 u 经过的城市数 + 1
						pre[v] = u ; 							// v 的先驱结点为 u
					}else if(happpMax[u] + happy[v] == happpMax[v]){ // 如果选择 u-->v 的路径 ，与之前获得最大开心值相同
						if(pass[u] + 1 < pass[v]){ 		// 经过的点更少，则平均值更大 
							pass[v] = pass[u] + 1 ;		// 起点到点 v 经过的城市数，等于起点到点 u 经过的城市数 + 1
							pre[v] = u ; 				// v 的先驱结点为 u
						}
					}
				}
			}
		}
	}
}
// 从终点开始，利用每个结点的先驱节点倒推，得到满足要求的路径，本函数可用一个while迭代来实现
void findRoute(int vt){ 
	if(vt == 0) {
		ansRoute.push_back(vt) ;
		return ;
	}
	ansRoute.push_back(vt) ;
	findRoute(pre[vt]) ;
}
int main(){
	fill(g[0] , g[0] + maxn * maxn , inf) ; // 初始化 图
	cin >> n >> k >> st ;
	si[st] = 0 ;
	is[0] = st ;
	for(int i = 1 ; i < n ; i ++){
		cin >> tem >> happy[i] ;
		si[tem] = i ;
		is[i] = tem ;
	}
	for(int i = 0 ; i < k ; i ++){
		cin >> tem >> tem1 >> cost ;
		int a = si[tem] , b = si[tem1] ;
		g[a][b] = g[b][a] = cost ; // 邻接矩阵 
	}
	dijkstra(0) ;
	rom = si["ROM"] ;
	findRoute(rom) ;
	reverse(ansRoute.begin() , ansRoute.end()) ;
	cout << rnum[rom] << ' ' << d[rom] << ' ' << happpMax[rom] << ' ' << happpMax[rom] / pass[rom] << endl ;
	for(int i = 0 ; i < ansRoute.size() ; i ++){
		printf("%s%s" , (is[ansRoute[i]]).c_str() , ((i == ansRoute.size() - 1)?"\n":"->")) ;
	}
	return 0 ;
}