PAT 1087 All Roads Lead to Rome [dijkstra+DFS] [map处理int和string的相互转换]

最新推荐文章于 2021-09-05 10:12:41 发布

DayDreammerⅠ

最新推荐文章于 2021-09-05 10:12:41 发布

阅读量499

点赞数

分类专栏： PAT

本文链接：https://blog.csdn.net/Time504/article/details/89161101

版权

PAT 专栏收录该内容

100 篇文章

订阅专栏

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

--------------------------------------这是题目和解题的分割线--------------------------------------

又是一道dijkstra+DFS求解的问题。不过这回顶点不是数值而是字符串，可以用hash表/map来相互转换，hash表稍微麻烦一点，不能直接模拟进制转换，不然数组下标会很大，不方便访问，所以还是用map吧~map的用法和这道题有些相似 PAT 1034 Head of a Gang ，但要更加简单，因为不存在重复的情况，也就不需要用到函数了。

第一次提交的时候第二个测试点我通不过，想了想，才发现最短路径的条数搞错了。应该要定义全局变量，在遍历到边界时自增，而不能用dijkstra算法中vetor数组的size()，这样求解出来的只是（任意点到）终点的最短路径数，而不是起点到终点的。

还有一个要注意的地方是，平均值不要除以顶点数哈，应该除以边数。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#include<iostream>
using namespace std;

const int maxN = 300,INF = 0x7fffffff;
int G[maxN][maxN],visited[maxN],cos[maxN],happy[maxN];
int n,m;
map<int,string> intToString;
map<string,int> stringToInt;
vector<int> minPath[maxN],tmp,best;

//最短路径 
void dijkstra(int index)
{
	fill(visited,visited+maxN,0);
	fill(cos,cos+maxN,INF);
	cos[index] = 0;
	int i,j;
	for(i=0;i<n;i++)
	{
		int minE = INF,minV = index;
		for(j=0;j<n;j++)
		{
			if(!visited[j]&&cos[j]<minE)
			{
				minE = cos[j];
				minV = j;
			}
		}
		visited[minV] = 1;
		for(j=0;j<n;j++)
		{
			if(!visited[j]&&G[minV][j]!=INF)
			{
				if(cos[minV]+G[minV][j]<cos[j])
				{
					cos[j] = cos[minV]+G[minV][j];
					minPath[j].clear();
					minPath[j].push_back(minV);
				}
				else if(cos[minV]+G[minV][j]==cos[j])
					minPath[j].push_back(minV);
			}
		}
	}
}

int happyMax = 0,aveHappy = 0,numPath = 0;
void findBestPath(int index)
{
	int i;
	if(index==0)
	{
		numPath++; //最短路径数 
		tmp.push_back(index);
		int happySum = 0;
		for(i=0;i<tmp.size();i++)
			happySum += happy[tmp[i]];
		if(happySum>happyMax)
		{
			best = tmp;
			happyMax = happySum;
			//平均值除以顶点数字-1（即边数） 
			aveHappy = happySum/(tmp.size()-1);
		}		
		else if(happySum==happyMax&&happySum/(tmp.size()-1)>aveHappy)
		{
			best = tmp;
			aveHappy = happySum/(tmp.size()-1);
		}
		tmp.pop_back();
		return;
	}
	tmp.push_back(index);
	for(i=0;i<minPath[index].size();i++)
		findBestPath(minPath[index][i]);
	tmp.pop_back();
}

int main()
{
	int i,j,hap;
	string begin,str;
	fill(G[0],G[0]+maxN*maxN,INF);
	fill(happy,happy+maxN,0);
	cin>>n>>m>>begin;
	//起点的对应值为0，方便计算 
	stringToInt[begin] = 0;
	intToString[0] = begin;
	for(i=1;i<=n-1;i++)
	{
		cin>>str>>hap;
		//其他顶点直接按1~n-1的顺序相互转换一下 
		stringToInt[str] = i;
		intToString[i] = str;
		happy[i] = hap;
	}
	for(i=0;i<m;i++)
	{
		string str1,str2;
		int cost;
		cin>>str1>>str2>>cost;
		//前面转换完毕，这里就可以直接拿来用了 
		int newX = stringToInt[str1];
		int newY = stringToInt[str2];
		G[newX][newY] = G[newY][newX] = cost;
	}
	dijkstra(0);
	int intEnd = stringToInt["ROM"];
	findBestPath(intEnd);	
	//最短路径数不能用 minPath[intEnd].size()来表示！！！ 
	printf("%d %d %d %d\n",numPath,cos[intEnd],happyMax,aveHappy);
	for(i=best.size()-1;i>0;i--)
		cout<<intToString[best[i]]<<"->";
	cout<<"ROM"<<endl; 
	return 0;
}