[PAT-A 1072]Gas Station
程序员文章站
2022-06-07 11:44:10
...
题目大意:
有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;
}