PAT-Advanced Level-1002-All Roads Lead to Rome

古城微笑少年丶 2022-04-16 06:06 80阅读 0赞

**PAT-Advanced Level-1002-All Roads Lead to Rome**

**题目链接：**[All Roads Lead to Rome][]

**题目大意：**

除起点外每个顶点都有幸运值，寻找一条最短路径到ROM（Rome），若存在多条路径，找出其中幸运值总和最大的路径，若总和相等，找出幸运值平均值最大的路径。

**题目分析：**

Dijkstra+DFS

*详见类同题目的分析：*[PAT-Advanced Level-1001-Public Bike Management][]

**PAT甲级题解：**[PAT\_ProgramAnswer][PAT_ProgramAnswer]

**代码：**

#include<iostream>
    #include<map>
    #include<string>
    #include<vector>
    #define MAX_SIZE 210		
    #define INF 1<<30
    #define Start 1		  //the Start Point of PATH
    using namespace std;
    //store information of every city
    map<string, int> Cities;			
    map<int, string> CitiesName;
    int Happiness[MAX_SIZE];
    
    int N, K;	//city num ,the num of route
    int CitiesMap[MAX_SIZE][MAX_SIZE];		
    int RouteCost[MAX_SIZE];		//represent the least cost from start to i
    bool Vis[MAX_SIZE];			//Visit Sysbom of every city
    vector<int> LeastRoutes[MAX_SIZE];	//store total shortest paths
    
    void Init()
    {
    	for (int i = 0; i < MAX_SIZE; i++)
    		for (int j = 0; j < MAX_SIZE; j++)
    			CitiesMap[i][j] = INF;
    }
    
    void Dijkstra()
    {
    	int i, j, k, MIN;
    	for (i = 1; i <= N; i++)
    	{
    		Vis[i] = false;
    		RouteCost[i] = CitiesMap[Start][i];
    		LeastRoutes[i].push_back(Start);
    	}
    	Vis[Start] = true;
    	for (i = 1; i <= N; i++)
    	{
    		MIN = INF;
    		for (j = 1; j <= N; j++)
    		{
    			if (!Vis[j] && RouteCost[j] < MIN)
    			{
    				k = j;
    				MIN = RouteCost[j];
    			}
    		}
    		Vis[k] = true;
    		for (j = 1; j <= N; j++)
    		{
    			if (!Vis[j] && RouteCost[k] + CitiesMap[k][j] < RouteCost[j])
    			{
    				RouteCost[j] = RouteCost[k] + CitiesMap[k][j];
    				LeastRoutes[j].clear();
    				LeastRoutes[j].push_back(k);
    			}
    			else if (!Vis[j] && RouteCost[k] + CitiesMap[k][j] == RouteCost[j])
    				LeastRoutes[j].push_back(k); 
    		}
    	}
    }
    int RouteNum=0;		//the number of shortest paths
    int TotalHappiness=0, AverHappiness = 0;		//record the maximum result
    vector<int> TmpPath;		//one shortest path in DFS pricess 
    vector<int> Res;			//record result shortest path 
    void DFS(int v)
    {
    	if (v == Start)		// produce a compete shortest path 
    	{
    		RouteNum++;		//add one 
    		int Total = 0;
    		TmpPath.push_back(v);
    		int CityInRoute = TmpPath.size() - 1;
    		for (int i =CityInRoute; i >= 0; i--)	
    			Total += Happiness[TmpPath[i]];	//cal the sum of happiness 
    		if (Total>TotalHappiness)		
    		{
    			AverHappiness = (int)(Total / CityInRoute);
    			TotalHappiness = Total;
    			Res = TmpPath;
    		}
    		else if (Total == TotalHappiness)	
    		{
    			//choose a path with large averager 
    			if ((int)(Total / CityInRoute) > AverHappiness)
    			{
    				AverHappiness = (int)(Total / CityInRoute);
    				Res = TmpPath;
    			}
    		}
    		TmpPath.pop_back();		//backtracking~
    		return;
    	}
    	TmpPath.push_back(v);
    	for (int i = 0; i < LeastRoutes[v].size(); i++)
    		DFS(LeastRoutes[v][i]);		//traverse all paths below this point
    	TmpPath.pop_back();		//backtracking~
    }
    
    
    int main()
    {
    	Init();
    	string CityName;
    	int happiness;
    	cin >> N >> K >> CityName;
    	Cities[CityName] = 1;
    	CitiesName[1] = CityName;
    	Happiness[1] = 0;
    	for (int i = 2; i <= N; i++)
    	{
    		cin >> CityName >> happiness;
    		Cities[CityName] = i;
    		Happiness[i] = happiness;
    		CitiesName[i] = CityName;
    	}
    	while (K--)
    	{
    		string u, v;
    		int cost;
    		cin >> u >> v >> cost;
    		CitiesMap[Cities[u]][Cities[v]] = cost;
    		CitiesMap[Cities[v]][Cities[u]] = cost;
    	}
    	Dijkstra();
    
    	DFS(Cities["ROM"]);
    	cout << RouteNum << " " << RouteCost[Cities["ROM"]] << " " << TotalHappiness << " " << AverHappiness << endl;
    	for (int i = Res.size() - 1; i >= 0; i--)
    	{
    		if (i != Res.size() - 1)
    			cout << "->";
    		cout << CitiesName[Res[i]];
    	}
    	cout << endl;
    	return 0;
    }

[All Roads Lead to Rome]: https://www.nowcoder.com/pat/5/problem/4315
[PAT-Advanced Level-1001-Public Bike Management]: https://blog.csdn.net/SZU_Crayon/article/details/84146848
[PAT_ProgramAnswer]: https://github.com/ZhuoZhuoCrayon/PAT_ProgramAnswer