欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[PAT-A 1072]Gas Station

程序员文章站 2022-06-07 11:44:10
...

[PAT-A 1072]Gas Station
[PAT-A 1072]Gas Station
题目大意:
有N所居民房,M个加油站,以及K条无向边。
现在要在M个加油站待选点中找见以一个来建造,要求:
1)该加油站离最近的居民房尽可能远。
2)该加油站离所有居民房的平均距离尽可能近。
3)所有房子与该加油站的距离不超出服务范围ds。

给出N M K DS以及K条无向边的边权,输出应当选择的加油站编号,与该加油站最近的居民房的距离,与所有居民房的平均距离。

思路:
1)编号的处理:加油站以编号G开头,将所有的加油站排在居民房后面,即用G后面的数字加上n作为加油站的编号。
2)枚举所有加油站,分别使用dijkstra算法计算每个加油站到每个居民房的最短距离。
3)获得最短距离数组d之后,对d进行遍历,判断每一项是否大于ds,记录最小值,平均值,按要求输出。
4)本题不需要保存路劲,只需要计算距离,计算的时候所有包含加油站的边都是真实存在的,也必须参与计算。

AC代码:

//PAT_A 1072
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxv = 1020;
const int inf = 0x3fffffff;
int n, m, k, ds, G[maxv][maxv];
bool vis[maxv] = { false };
int d[maxv];
void dijkstra(int s) {
	fill(vis, vis + maxv, false);
	fill(d, d + maxv, inf);
	d[s] = 0;
	for (int i = 0; i < n + m; i++) {
		int u = -1, MIN = inf;
		for (int j = 1; j <= n + m; j++) {
			if (vis[j] == false && d[j] < MIN) {
				MIN = d[j];
				u = j;
			}
		}
		if (u == -1)return;
		vis[u] = true;
		for (int v = 1; v <= n + m; v++) {
			if (vis[v] == false && G[u][v] != inf) {
				if (d[v] > d[u] + G[u][v]) {
					d[v] = d[u] + G[u][v];
				}
			}
		}
	}
}
int getID(char str[]) {
	int i = 0, len = strlen(str), id = 0;
	while (i < len) {
		if (str[i] != 'G') {
			id = id * 10 + (str[i] - '0');
		}
		i++;
	}
	if (str[0] == 'G')return n + id;//加油站排在居民房的后面
	else return id;
}
int main() {
	(void)scanf("%d %d %d %d", &n, &m, &k, &ds);
	int u, v, w;
	char city1[5], city2[5];
	fill(G[0], G[0] + maxv * maxv, inf);
	for (int i = 0; i < k; i++) {
		(void)scanf("%s %s %d", city1, city2, &w);
		u = getID(city1), v = getID(city2);
		G[u][v] = w;
		G[v][u] = w;
	}
	double ansDis = -1, ansAvg = inf;//最短距离,最短平均距离
	int ansID = -1;//最终加油站
	for (int i = n + 1; i <= n + m; i++) {
		double minDis = inf, avg = 0;
		dijkstra(i);
		for (int j = 1; j <= n; j++) {
			if (d[j] > ds) {
				minDis = -1;
				break;
			}
			if (d[j] < minDis)minDis = d[j];
			avg += 1.0 * d[j] / n;
		}
		if (minDis == -1)continue;
		if (minDis > ansDis) {//优先输出最短距离最大的
			ansID = i;
			ansDis = minDis;
			ansAvg = avg;
		}
		else if (minDis == ansDis && avg < ansAvg) {//最短距离相同,输出平均距离最小的
			ansID = i;
			ansAvg = avg;
		}
	}
	if (ansID == -1)printf("No Solution\n");
	else {
		printf("G%d\n", ansID - n);
		printf("%.1f %.1f", ansDis, ansAvg);
	}
	return 0;
}
相关标签: PAT-A