PAT 1087 All Roads Lead to Rome

小鱼儿 2023-07-10 15:49 2阅读 0赞

### 有很多误区和注意点我都在代码里面通过注释的方式注明了。 ###

### 使用SPFA算法写的，主要是想练习一下这个算法，完全可以使用Dijkstra，而且我个人更喜欢Dijkstra，毕竟复杂度很稳定，SPFA容易被卡数据点，导致复杂度特别大。 ###

### ***下面有中文解释*** ***下面有中文解释***  ***下面有中文解释***  ###

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

题目大意：有N个城市，M条无向边。现在需要从某个给定的起始城市出发（除了起始城市外，其  
他每个城市都有一个“幸福值”），前往名为“ROM”的城市。给出每条边所需要消耗的花费,  
求从起始城市出发，到达城市ROM所需要的最少花费，并输出最少花费的路径。如果这样  
的路径有多条，则选择路径上城市的“幸福值”之和最大的那条。如果路径仍然不唯一，则  
选择路径上城市的平均幸福值最大的那条。

输入：

第一行有三个数据：城市个数N、边的个数M、起始城市

接下来有N-1行数据：城市名称 城市的幸福值

接下来有M行数据：城市名称 城市名称 花费

输出：

第一行：最短路径数、最短路径值、最大幸福值和、最大平均幸福值

第二行：从起始城市到ROM城市的路径

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    #include<deque> 
    #include<map>
    #include<unordered_map>
    #include<set>
    #include<sstream>
    using namespace std;
    const int MAXN = 202; 
    const int INF = 10000000;
    
    struct Node{
    	int v;
    	int cost;
    	Node(int v,int cost){
    		this->v = v;
    		this->cost = cost;
    	}
    };
    //从字符串到数字的对应关系以及从数字到字符串的对应关系
    /*
    ** 如在例子中
    ** HZH--0  ROM--1  PKN--2  GDN--3   PRS--4  BLN--5 
    */ 
    map<string,int> cityToIndex;
    map<int,string> indexToCity;
    
    //最小路径有关的变量： 
    vector<Node> adj[MAXN];
    int dis[MAXN]; 
    bool vis[MAXN] = {false};  //节点是否在队列中 
    
    //最大点权和以及最大平均点权相关的变量： 
    int happy[MAXN] = {0};  //各个节点的点权（幸福值） 
    int maxPointSum = -1;  //最大点权和 
    int maxAvgPoint = -1;  //平均点权和 
    
    //路径相关的变量： 
    int num;  //最短路径(按照u--->v的花费计算的)有几条 
    set<int> pre[MAXN];  //pre[u]表示：u的前驱节点有哪些 
    vector<int> path;  //根据第一、第二、第三标尺（u-->v的花费，最大点权和，最大平均点权）计算的最短路径 
    vector<int> temppath; //临时路径 
    
    deque<int> choose; 
    
    /*
    ** SPFA只负责把所有最短路径找出来（根据第一标尺，也就是从u---->v的花费）
    ** 对于如果有多条最短路径时找出幸福值总和最大的最短路径
    ** 以及如果有多条最短路径且幸福值总和一样大时找平均幸福值最大的最短路径
    ** 我们交给DFS去做。 
    */
    void SPFA(int s,int n){
    	fill(dis,dis+n,INF);
    	dis[s] = 0;
    	int u,v,cost;
    	choose.push_back(s);
    	vis[s] = true;
    	while(!choose.empty()){
    		u = choose.front();
    		choose.pop_front();
    		vis[u] = false;
    		for(int i=0;i<adj[u].size();i++){
    			v = adj[u][i].v;
    			cost = adj[u][i].cost;
    			if(dis[v] > dis[u] + cost){
    				dis[v] = dis[u] + cost;
    				//误区3：记得要先把pre之前的前驱节点都删除。 
    				pre[v].clear();
    				//注意点1：这个地方要使用set而不能使用vector，因为这个前驱节点会加入多次，使用set可以自动去重。 
    				//另外：我们在Dijkstra中用的是vector，因为Dijkstra算法中每条边只会松弛一次，这个u也只会加入一次。
    				//而SPFA算法中每条边最多会松弛v-1次，这个u也就不止加入一次。 
    				pre[v].insert(u);
    				if(!vis[v]){
    					choose.push_back(v);
    					vis[u] = true;
    				}
    			}else if(dis[v] == dis[u] + cost){
    				pre[v].insert(u);
    			}	
    		}
    	}
    }
    
    /*
    **遍历所有的最短路径，计算(最大点权和)和(最大平均点权)。 
    */
    void DFS(int u,int s){
    	if(u == s){
    		temppath.push_back(u);
    		num++;
    		int totalPoint = 0; 
    		double avgPoint;
    		//误区2：计算(当前路径上所有节点的点权和)和(当前路径每个节点的平均点权)的时候不考虑起始顶点 
    		for(int i=0;i<temppath.size()-1;i++){
    			int u = temppath[i];
    			totalPoint += happy[u];
    		}
    		//误区1：计算avgPoint时候别忘了加括号，我就因为这个括号找了半小时的错误。 
    		//误区2：计算(当前路径上所有节点的点权和)和(当前路径每个节点的平均点权)的时候不考虑起始顶点 
    		avgPoint = 1.0*totalPoint / (temppath.size()-1);
    		if(totalPoint > maxPointSum){
    			maxPointSum = totalPoint;
    			maxAvgPoint = avgPoint;
    			path = temppath;
    		}else if(totalPoint == maxPointSum && avgPoint > maxAvgPoint){
    			maxAvgPoint = avgPoint;
    			path = temppath;
    		}
    		//注意点2：别忘了pop_back(); 
    		temppath.pop_back();
    		return ;
    	}
    	temppath.push_back(u);
    	for(auto it=pre[u].begin();it!=pre[u].end();it++){
    		DFS(*it,s);
    	}
    	temppath.pop_back();
    }
    
    void printPath(){
    	for(int i=path.size()-1;i>0;i--){
    		cout<<indexToCity[path[i]]<<"->";
    	}
    	cout<<indexToCity[path[0]]<<endl;
    }
    
    int main(){
    	string source;
    	string name;
    	string start,end;
    	int n,m,s,t;
    	int u,v;
    	int value;
    	cin>>n>>m>>source;
    	s = 0;
    	cityToIndex[source] = 0;
    	indexToCity[0] = source;
    	for(int i=1;i<n;i++){
    		cin>>name>>value;
    		if(name=="ROM"){
    			t = i; //记录终点（ROM）对应的数字。 
    		}
    		cityToIndex[name] = i;
    		indexToCity[i] = name;
    		happy[i] = value;
    	}
    	while(m--){
    		cin>>start>>end>>value;
    		u = cityToIndex[start];
    		v = cityToIndex[end];
    		adj[u].push_back(Node(v,value));
    		adj[v].push_back(Node(u,value));
    	}
    	SPFA(s,n);
    	DFS(t,s);
    	cout<<num<<" "<<dis[t]<<" "<<maxPointSum<<" "<<maxAvgPoint<<endl;
    	printPath();
    	return 0; 
    }