1087 All Roads Lead to Rome (30 分) dijstra+dfs 输出最短路路径+条数

向右看齐 2021-11-04 13:36 266阅读 0赞

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

**题意：**6个结点，7条路，从HZH出发（到达ROM）

除了起始节点外，经过每个节点的幸福数。

然后每条双向边的起始点，终点，花费。

输出最短路的条数，最短路的花费，总共可以得到的幸福数，幸福数平均值（幸福总数/经过的结点--不包括起点）

**思路：**用dijstra跑出最短路的同时最大幸福数，然后用dfs回溯找到平均值最大的。

PS：一开始做没有在意输出的是平均数，路径用int pre\[\]数组记录的，然后改成dfs回溯之后，pre改成了vector，然后初始化的  
memset(pre,0,sizeof pre);没有删掉，运行一直正确，提交一直段错误，崩溃了二十分钟呜呜呜

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <vector>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    int ma[1005][1005];
    int hap[1005];//结点的幸福数 
    int dis[1005];//起点到结点的距离
    int sum[1005];//记录幸福总数
    int num[1005];//最短路条数 
    int vis[1005];
    map<string,int> ys;//映射 
    map<int,string> ys2;//反映射 
    int n,m,e;
    vector<int> pre[1005],path,temppath;
    int maxvalue;
    double maxavg;
    void dfs(int v)
    {
    	temppath.push_back(v);
    	if(v==0)
    	{
    		int value=0;
    		for(int i=0;i<temppath.size();i++) 
    		value+=hap[temppath[i]];
    		double tempavg=1.0*value/(temppath.size()-1);
    		if(value>maxvalue) 
    		{
    			maxvalue=value;
    			maxavg=tempavg;
    			path=temppath;
    		} 
    		else if(value==maxvalue&&tempavg>maxavg) 
    		{
    			maxavg=tempavg;
    			path=temppath;
    		}
    		temppath.pop_back();
    		return;
    	}
    	for(int i=0;i<pre[v].size();i++)
    	dfs(pre[v][i]);
    	temppath.pop_back();
    }
    
    int main()
    {
    	int i,j,k,next;
    	string c,c1,c2;	
    	memset(ma,INF,sizeof ma);
    	memset(dis,INF,sizeof dis);
    	memset(sum,0,sizeof sum);
    	memset(num,0,sizeof num);
    	memset(vis,0,sizeof vis);
    	cin>>n>>m>>c;
    	ys[c]=0;
    	ys2[0]=c;
    	
    	for(i=1;i<n;i++)
    	{
    		cin>>c1>>k;
    		if(c1=="ROM") e=i;//记录终点 
    		ys[c1]=i;
    		ys2[i]=c1; 
    		hap[i]=k; 
    	}
    	for(i=0;i<m;i++)
    	{
    		cin>>c1>>c2>>k;
    		ma[ys[c1]][ys[c2]]=ma[ys[c2]][ys[c1]]=k;
    	}
    	
    	hap[0]=0;
    	sum[0]=0;
    	num[0]=1;
    	dis[0]=0;
    	for(i=0;i<n;i++)
    	{
    		int d=INF;
    		for(j=0;j<n;j++)
    		{
    			if(vis[j]==0&&dis[j]<d)
    			{
    				d=dis[j];
    				next=j;
    			}
    		}
    		vis[next]=1;
    		for(j=0;j<n;j++)
    		{
    			if(dis[j]>dis[next]+ma[next][j])
    			{
    				dis[j]=dis[next]+ma[next][j];
    				sum[j]=sum[next]+hap[j];
    				num[j]=num[next];
    				pre[j].clear();
    				pre[j].push_back(next);
    			}
    			else if(dis[j]==dis[next]+ma[next][j])
    			{
    				num[j]+=num[next];
    				if(sum[j]<sum[next]+hap[j])
    				{
    					sum[j]=sum[next]+hap[j];
    				 	pre[j].push_back(next);
    				}			
    			}
    		}
    	}
    	dfs(e);
    	printf("%d %d %d %d\n",num[e],dis[e],sum[e],(int)maxavg);
    	for(i=path.size()-1;i>0;i--)
    	cout<<ys2[path[i]]<<"->";
    	cout<<"ROM"<<endl;
    }