PAT A1087 All Roads Lead to Rome (30point(s))

Scroll Down

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.

分析

求出代价最小的路径,如果代价相等,则选择幸福值最大的那条路径,如果幸福值仍相等,则求出平均幸福值最大的那条路径,该路径一定是唯一的。最后输出拥有最小代价的路径条数、最小代价、最大幸福值、平均幸福值和完整路径。

解答

本题是最短路径问题,因此采用dijkstra算法。因为点用地名也就是字符串表示,所以为了简化问题,需要用map将字符串映射到数字,用字符串数组将数字映射到字符串。

  1. 求拥有最小代价的路径条数:用cnt数组记录,当遍历到第k个点时,如果代价更小,令cnt[k] = cnt[minIndex],注意不是令cnt[k]为1,因为到达minIndex的路径也可能有多条;如果代价相等,令cnt[k] = cnt[minIndex] + cnt[k],这里同样不能简单地令cnt[k] = cnt[minIndex],因为从minIndex到达的路径一定是新路径,所以要加到之前的cnt[k]当中。
  2. 求最大幸福值,与dijkstra算法中求最小代价的方法一致
  3. 求完整路径,用pre标记每个点的前缀。
  4. 在计算minCost + cost[minIndex][k]一定要保证minIndex与k是连通的,否则因为cost[minIndex][k] = INT_MAX,所以会导致minCost + cost[minIndex][k]溢出变为负数,使结果出错。
  5. 本题不考虑代价相等,幸福值相等的情况也能AC,可能测试样例不全。
#include<iostream>
#include<string>
#include<unordered_map>
#include<vector>
#include<climits>
#include<stack>

using namespace std;

int main() {
	int cn, rn;
	string from, tmp1, tmp2;
	cin >> cn >> rn >> from;
	unordered_map<string, int> cityIndex;
	vector<string> cities(cn);
	vector<int> happiness(cn);
	vector<vector<int>> cost(cn, vector<int>(cn, INT_MAX));

	cityIndex[from] = 0;
	cities[0] = from;
	for (int i = 1; i < cn; i++) {
		cin >> cities[i] >> happiness[i];
		cityIndex[cities[i]] = i;
	}

	for (int i = 0; i < rn; i++) {
		int c;
		cin >> tmp1 >> tmp2 >> c;
		int m = cityIndex[tmp1], n = cityIndex[tmp2];
		cost[m][n] = cost[n][m] = c;
	}

	int start = cityIndex[from], end = cityIndex["ROM"];
	vector<int> dist(cn, INT_MAX), pre(cn), maxHappiness(cn, 0);
	vector<int> visited(cn, 0), cnt(cn, 0), citiesCount(cn, 0);
	dist[start] = 0;
	cnt[start] = 1;
	for (int i = 0; i < cn; i++) pre[i] = i;
	for (int i = 0; i < cn; i++) {
		int minCost = INT_MAX, minIndex = -1;
		
		for (int k = 0; k < cn; k++) {
			if (!visited[k] && dist[k] < minCost) {
				minCost = dist[k];
				minIndex = k;
			}
		}
		visited[minIndex] = 1;
		
		for (int k = 0; k < cn; k++) {
			if (visited[k] || cost[minIndex][k] == INT_MAX) continue;
			if (minCost + cost[minIndex][k] == dist[k]) 
				cnt[k] += cnt[minIndex];
			else if (minCost + cost[minIndex][k] < dist[k]) 
				cnt[k] = cnt[minIndex];

			if (minCost + cost[minIndex][k] < dist[k] || 
				(minCost + cost[minIndex][k] == dist[k] && 
				maxHappiness[minIndex] + happiness[k] > maxHappiness[k])/* ||
				( minCost + cost[minIndex][k] == dist[k] &&
				maxHappiness[minIndex] + happiness[k] == maxHappiness[k]) &&
				citiesCount[minIndex]+1< citiesCount[k]*/) {
				dist[k] = minCost + cost[minIndex][k];
				pre[k] = minIndex;
				maxHappiness[k] = maxHappiness[minIndex] + happiness[k];
				citiesCount[k] = citiesCount[minIndex] + 1;
			}
		}
	}

	stack<string> path;
	int i = end;
	while (i != pre[i]) {
		path.push(cities[i]);
		i = pre[i];
	}
	path.push(cities[i]);

	printf("%d %d %d %d\n", cnt[end], dist[end], maxHappiness[end],
		maxHappiness[end] / (path.size() - 1));
	printf("%s", path.top().c_str());
	path.pop();
	while (!path.empty()) {
		printf("->%s", path.top().c_str());
		path.pop();
	}
	return 0;
}