PAT 甲级 A1087 All Roads Lead to Rome

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

题意：

6 7 HZH（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
 
//输出
3 3 195 97（最短路径的条数， 最短距离， 最大点权和， 和该路径下的平均点权）；
HZH->PRS->ROM(最优解的路径)
 
//优先级：距离>点权和>平均点权;

①只用Dijkstra算法：
 

#include
#include
#include 
#include
using namespace std;
const int maxn = 1010;
const int INF = 1 << 30 - 1;
bool vis[maxn] = {false};
int weight[maxn];//点权; 
int d[maxn], w[maxn], pt[maxn], num[maxn], pre[maxn];
//最短距离，最大点权和， 最短距离结点个数 ， 最短距离条数， 最优路径; 
int G[maxn][maxn];
mapint> stringToNum;
map<int, string> numToString;
int n,m;
void Dijkstra(int st) {
	fill(d, d + maxn, INF);
	memset(w, 0, sizeof(w));
	memset(pt, 0, sizeof(pt));
	memset(num, 0, sizeof(num));
	num[st] = 1;//起码都有一条，不然去那都是0; 
	d[st] = 0;
	w[st] = weight[st];//w初始化; 
	for(int i = 0; i < n; i++) {
		pre[i] = i;
	}
	for(int i = 0; i < n; i++) {
		int u = -1, MIN = INF;
		for(int j = 0 ;j < n; j++) {
			if(vis[j] == false && d[j] < MIN) {
				MIN = d[j];
				u = j;
			} 
		}
		if(u == -1) return ;
		vis[u] = true;
		for(int v = 0; v < n; v++) {
 			if(vis[v] == false && G[u][v] != INF) {
 				if(d[u] + G[u][v] < d[v]) {
 					d[v] = d[u] + G[u][v];
 					w[v] = w[u] + weight[v];
 					num[v] = num[u];
					pre[v] = u; 
					pt[v] = pt[u] + 1;
				 }else if(d[u] + G[u][v] == d[v]) {
				 	num[v] += num[u];//最短距离下有新路;
					//根据点权和最佳路径更新;
					 
				 	if(w[u] + weight[v] > w[v]) {//标准1同， 找最大点权和的那条路 
				 		w[v] = w[u] + weight[v];
				 		//num[v] += num[u];//去v有多了一个最短路径的结点u，应该是+=; 
				 		pre[v] = u;
				 		pt[v] = pt[u] + 1;//换路了路上的节点数跟着改变; 
					 } else if(w[u] + weight[v] == w[v]) {//如果标准2也相同; 
							double uAvg = 1.0 * (w[u] + weight[v]) / (pt[u] + 1);//新的路的平均点权;
							double vAvg = 1.0 * w[v] / pt[v];//旧路;   
				 		if(uAvg > vAvg) {
				 			pre[v] = u;
				 			pt[v] = pt[u] + 1;				 		
						 }
					 }
				 }
			 }
		} 
	}
} 
 
void DFS(int v) {
	if(v == 0) {
		cout<
		return ;
	}
	DFS(pre[v]);
	cout<<"->"<
}
 
 
int main() {
	string str;
	cin >> n >> m >> str;
	stringToNum[str] = 0;//起点编号; 
	numToString[0] = str;
	for(int i = 1; i < n; i++) {
		cin>>str>>weight[i];
		stringToNum[str] = i; //映射; 
		numToString[i] = str;
	}
	fill(G[0], G[0] + maxn * maxn, INF);
	for(int i = 0; i < m; i++) {
		string str1, str2;
		int u, v, w;
		cin>>str1>>str2>>w;
		u = stringToNum[str1];
		v = stringToNum[str2];
		G[u][v] = w;//无向连通图; 
		G[v][u] = w;
	}//建图; 
	Dijkstra(0);
	int ed = stringToNum["ROM"];
	printf("%d %d %d %d\n", num[ed], d[ed], w[ed], w[ed] / pt[ed]);
	DFS(ed);//输出路径; 
	return 0;
}

②Dijkstra + DFS

Dijkstra找出所有最短路径

DFS遍历路径，找出点权和最大或点权和最大且平均点权最大的路径

#include
#include
#include
#include 
#include
using namespace std;
const int maxn = 1010;
const int INF = 1 << 30 - 1;
bool vis[maxn] = {false};
int weight[maxn];//点权; 
int d[maxn];
//最短距离，最大点权和， 最短距离结点个数 ， 最短距离条数， 最优路径; 
int G[maxn][maxn];
mapint> stringToNum;
map<int, string> numToString;
int n,m;
 
//Dijkstra只负责找最短路径;
vector<int > pre[maxn]; 
 
void Dijkstra(int st) {
	fill(d, d + maxn, INF);
	d[st] = 0;
	for(int i = 0; i < n; i++) {
		int u = -1, MIN = INF;
		for(int j = 0 ;j < n; j++) {
			if(vis[j] == false && d[j] < MIN) {
				MIN = d[j];
				u = j;
			} 
		}
		if(u == -1) return ;
		vis[u] = true;
		for(int v = 0; v < n; v++) {
 			if(vis[v] == false && G[u][v] != INF) {
 				if(d[u] + G[u][v] < d[v]) {
 						d[v] = d[u] + G[u][v];
 						pre[v].clear();
 						pre[v].push_back(u);
				 	} else if(d[u] + G[u][v] == d[v]) {
				 		
					pre[v].push_back(u);
				 }
			 }
		 }
	}
} 
 
//DFS遍历所有路最短径找到满足条件的最优路径; 
//该最短路径满足 点权和最大，平均点权最大； 
vector<int > tempPath, path;
int numPath = 0;
int  maxWeight = 0;
double maxAvg = 0;
void DFS(int v) {
	if(v == 0) {
		tempPath.push_back(v);
		int tempWeight = 0;double tempAvg = 0;
		numPath++;
		for(int i = tempPath.size() - 1; i >= 0; i--) {
			int id = tempPath[i];
			tempWeight += weight[id];
		}
		tempAvg = (1.0 * tempWeight) / (tempPath.size() - 1);
		if(tempWeight > maxWeight) {
			maxWeight = tempWeight ;
			maxAvg = tempAvg;
			path = tempPath;
		}else if(tempWeight == maxWeight && tempAvg > maxAvg) {
			maxAvg = tempAvg;
			path = tempPath;
		}
		tempPath.pop_back();
		return ;
	}
	tempPath.push_back(v);
	for(int i = 0; i < pre[v].size(); i++) {
		DFS(pre[v][i]);
	}
	tempPath.pop_back();
}
 
 
int main() {
	string str;
	cin >> n >> m >> str;
	stringToNum[str] = 0;//起点编号; 
	numToString[0] = str;
	for(int i = 1; i < n; i++) {
		cin>>str>>weight[i];
		stringToNum[str] = i; //映射; 
		numToString[i] = str;
	}
	fill(G[0], G[0] + maxn * maxn, INF);
	for(int i = 0; i < m; i++) {
		string str1, str2;
		int u, v, w;
		cin>>str1>>str2>>w;
		u = stringToNum[str1];
		v = stringToNum[str2];
		G[u][v] = w;//无向连通图; 
		G[v][u] = w;
	}//建图; 
	Dijkstra(0);//找到所有最短路径; 
	int ed = stringToNum["ROM"];
	DFS(ed);//找到最优路径; 
	printf("%d %d %d %d\n", numPath, d[ed], maxWeight, (int ) maxAvg);
	for(int i = path.size() - 1; i >= 0; i--) {
		int id = path[i];
		cout<
		if(i > 0) cout<<"->";
	} 
	return 0;
}