PAT(图)——1087 All Roads Lead to Rome （30 分）

1087 All Roads Lead to Rome （30 分）

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.

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.

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

题目大意：

给出城市通往城市的花费，每个城市给你带来的快乐值，求从起点到罗马的最短路径，当路径相同，先比较快乐值的大小，如果快乐值相同，比较平均快乐值。

题目解析：

发现这种求最短路径题都是一样的，直接迪杰斯特拉算法搞定，如果要输出沿途的路径就用pre保存前驱结点，本题还涉及到把建立string类型到int型的映射。此题跟PAT1003和PAT1030的套路一模一样。

具体代码：

#include<iostream>
#include<algorithm>
#include<map>
#include<climits>
using namespace std;
#define MAXN 210
struct node {
	string name;
	int happiness;
} A[MAXN];
map<string,int> m;
int e[MAXN][MAXN];
int dis[MAXN];//原点到i点的距离
int h[MAXN];//原点到i点的快乐值总数
int num[MAXN];//原点到i点的城市总数
int route[MAXN];//最短的路线总数
int pre[MAXN];//i点的前驱结点
bool vis[MAXN]= {false};
void dfs(int v){
	if(v==0){
		cout<<A[0].name;
		return;
	}
	dfs(pre[v]);
	cout<<"->"<<A[v].name;
}
int main() {
	fill(e[0],e[0]+MAXN*MAXN,INT_MAX);
	fill(dis,dis+MAXN,INT_MAX);
	int n,k;
	scanf("%d%d",&n,&k);
	string start,c1,c2;
	cin>>start;
	m[start]=0;
	A[0].name=start;
	for(int i=1; i<n; i++) {
		cin>>A[i].name>>A[i].happiness;
		m[A[i].name]=i;
	}
	while(k--) {
		int a;
		cin>>c1>>c2>>a;
		e[m[c1]][m[c2]]=e[m[c2]][m[c1]]=a;
	}
	dis[0]=0;
	h[0]=0;
	num[0]=1;
	pre[0]=0;
	route[0]=1;
	for(int i=0; i<n; i++) {
		int v=-1,min=INT_MAX;
		for(int j=0; j<n; j++) {
			if(vis[j]==false&&dis[j]<min) {
				v=j;
				min=dis[j];
			}
		}
		if(v==-1) break;
		vis[v]=true;
		for(int j=0; j<n; j++) {
			if(vis[j]==false&&e[v][j]<INT_MAX) {
				if(dis[j]>dis[v]+e[v][j]) { //如果找到更短的路径，更新
					route[j]=route[v];
					dis[j]=dis[v]+e[v][j];
					h[j]=h[v]+A[j].happiness;
					num[j]=num[v]+1;
					pre[j]=v;
				} else if(dis[j]==dis[v]+e[v][j]) { //如果距离相等
					route[j]+=route[v];
					if(h[j]<h[v]+A[j].happiness) { //如果新路径快乐值更大，更新
						h[j]=h[v]+A[j].happiness;
						num[j]=num[v]+1;
						pre[j]=v;
					} else if(h[j]==h[v]+A[j].happiness) { //如果连快乐值也相等
						if(num[j]>num[v]+1) {//如果路经的城市更少，则平均快乐值更高，更新
							num[j]=num[v]+1;
							pre[j]=v;
						}
					}
				}
			}
		}
	}
	int rom=m["ROM"];
	printf("%d %d %d %d\n",route[rom],dis[rom],h[rom],h[rom]/(num[rom]-1));
	dfs(rom);
	return 0;
}