PAT 1072 Gas Station [dijkstra]

A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range.

Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendation. If there are more than one solution, output the one with the smallest average distance to all the houses. If such a solution is still not unique, output the one with the smallest index number.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive integers: N (≤10​3​​), the total number of houses; M (≤10), the total number of the candidate locations for the gas stations; K (≤10​4​​), the number of roads connecting the houses and the gas stations; and D​S​​, the maximum service range of the gas station. It is hence assumed that all the houses are numbered from 1 to N, and all the candidate locations are numbered from G1 to GM.

Then K lines follow, each describes a road in the format

P1 P2 Dist

where P1 and P2 are the two ends of a road which can be either house numbers or gas station numbers, and Dist is the integer length of the road.

Output Specification:

For each test case, print in the first line the index number of the best location. In the next line, print the minimum and the average distances between the solution and all the houses. The numbers in a line must be separated by a space and be accurate up to 1 decimal place. If the solution does not exist, simply output No Solution.

Sample Input 1:

4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2

Sample Output 1:

G1
2.0 3.3

Sample Input 2:

2 1 2 10
1 G1 9
2 G1 20

Sample Output 2:

No Solution

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

这个题目的意思有一些绕口= = 先简单解读一下这句英文吧。

A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. 

粗体字部分用来描述加油站的位置情况。红色字体呢是说这个最短距离要尽可能的大。也就是加油站和居民楼的之间的距离。

简而言之，需要依次求出X个加油站距离所有居民楼的路径，再遍历该加油站，得出与该加油站最近的居民楼的距离。这样下来，会收获X个（加油站数量）最小距离，在其中求出最大解即可。如果相同，则选择平均距离最小的。还相同，序号最小。

需要注意的是：①居民楼和加油站的读取方式不一样，加油站前带有字母G，所以需要字符输入，并特殊处理一下。

②下标是从1开始，结束于M+N

#include<cstdio>
#include<algorithm>
#include<cstring>
const int maxN = 1080,INF = 0x3fffffff;

using namespace std;

int G[maxN][maxN],dis[maxN],vis[maxN];
int N,M,K,D;

void dijkstra(int index)
{
	//这个函数要循环多次，所以每次都要记得初始化 
	fill(vis,vis+maxN,0);
	fill(dis,dis+maxN,INF);
	dis[index] = 0;
	int i,j;
	for(i=1;i<=N+M;i++)
	{
		int minI = index,minN = INF;
		for(j=1;j<=N+M;j++)
		{
			if(!vis[j]&&dis[j]<minN)
			{
				minI = j;
				minN = dis[j];
			}
		}
		vis[minI] = 1;
		for(j=1;j<=M+N;j++)
		{
			if(!vis[j]&&G[minI][j]!=INF&&dis[minI]+G[minI][j]<dis[j])
				dis[j] = dis[minI]+G[minI][j];
		}
	}
}

//处理输入 
int charToInt(char s[])
{
	int st = 0,sum = 0;
	//如果是加油站，下一个位置才是数字 
	if(s[0]=='G') st = 1;
	//字符转整型 
	for(int i = st;i<strlen(s);i++)
		sum = sum*10+s[i]-'0';
	//将加油站序号顺序加入到居民楼后边 
	if(s[0]=='G') return sum+N;
	return sum;
}

int main()
{
	int i,j;
	scanf("%d%d%d%d",&N,&M,&K,&D);
	fill(G[0],G[0]+maxN*maxN,INF);
	//下标从1开始 
	for(i=1;i<=K;i++)
	{
		char x[10],y[10];int d;
		scanf("%s%s%d",&x,&y,&d);
		int newX = charToInt(x);
		int newY = charToInt(y);
		//无向边 
		G[newX][newY] = G[newY][newX] = d;
	}
	//最小距离中的最大长度，最小平均值，最合适的加油站 
	int maxDis = -1,minAve = INF,bestV;
	for(i=N+1;i<=N+M;i++)
	{
		dijkstra(i);
		//临时平均值，临时距离 
		int tmpAve = 0,tmpDis = INF;
		//遍历找到与该加油站距离最短的居民楼 
		for(j=1;j<=N;j++)
		{
			tmpAve += dis[j]; //平均值 
			if(dis[j]>D) //如果超出所给范围，不算数 
			{
				tmpDis = -1; //用特殊值标记一下 
				break;
			}
			//更新该加油站的最小距离 
			if(dis[j]<tmpDis) tmpDis = dis[j];
		}
		//如果超出了范围，就不往下判断了 
		if(tmpDis==-1)	continue;
		//更新最大的最小距离 
		if(tmpDis>maxDis)
		{
			maxDis = tmpDis;
			minAve = tmpAve;
			bestV = i;
		}
		//如果相等，用平均值判断
		//由于这里平均值是<不是<=，所以只会存下序号最小的值 
		else if(tmpDis==maxDis&&tmpAve<minAve)
		{
			minAve = tmpAve;
			bestV = i;
		}
	}
	if(maxDis==-1)
		printf("No Solution\n");
	else
		printf("G%d\n%.1f %.1f",bestV-N,maxDis*1.0,minAve*1.0/N);
	return 0;
}