PTA甲级 1072 Gas Station (30分)
强烈推荐,刷PTA的朋友都认识一下柳神–PTA解法大佬
本文由参考于柳神博客写成
还有就是非常非常有用的 算法笔记 全名是
算法笔记 上级训练实战指南 //这本都是PTA的题解
算法笔记
PS 今天也要加油鸭
题目原文
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 (≤103), the total number of houses; M (≤10), the total number of the candidate locations for the gas stations; K (≤104), 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
生词如下:
PS:这题也看懂了,同样的属于不会做系列.
题意:
有N所居民房,M个加油站待建点.让你在这些点中选一个出来.
这个点加油站的点要离最近的居民房尽可能的远,而且保证所有房子离这个加油站的距离不超过给定的服务范围DS.现在给出N,M,K,DS,以及K条无向边的端点以及边权.输出选择的加油站编号.与改加油站最近的居民房的编号.改加油站距离所有居民房的平均距离.如果有多个最近距离相同的解.
思路如下:
把加油站也作为一个结点录入进入.
然后就是正常的Dijkstra算法.
就是要注意我们要多次使用Dijkstra算法.
代码如下:
#include<iostream>
#include<cstring>
using namespace std;
const int MAXV = 2050; //数组的最大
const int INF = 1000000000; //表示无穷大的一个数
int G[MAXV][MAXV];
char gas1[6], gas2[6];
int n, m, k, ds,t,d[MAXV];
bool vis[MAXV] = { false };
int getID(char p[]) { //获得ID的函数
int len = strlen(p),ID=0;
for (int i = 0; i < len; ++i) {
if (p[i] != 'G') ID = ID * 10 + (p[i] - '0');
}
if (p[0]=='G') return ID + n;
else return ID;
}
void Dijkstra(int s) {
fill(d, d + MAXV, INF);
fill(vis, vis + MAXV, false);
d[s] = 0;
for (int i = 1; i <= n + m; i++) {
int u = -1, MIN = INF;
for (int j = 1; j <= n + m; ++j) {
if (!vis[j] && 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] && G[u][v] != INF) {
if (d[v] > d[u] + G[u][v]) {
d[v] = d[u] + G[u][v];
}
}
}
}
}
int main(void) {
scanf("%d%d%d%d", &n, &m, &k, &ds);
fill(G[0], G[0]+MAXV*MAXV, INF);
for (int i = 0; i < k; ++i) {
int u, v;
scanf("%s %s %d", gas1, gas2, &t);
u = getID(gas1);
v = getID(gas2);
G[u][v] = G[v][u] = t;
}
double ansAve = INF,ansDis=-1;
int index = -1;
for (int i = n+1; i <= n + m; i++) {
Dijkstra(i);
double tempAve = 0,tempDis=INF;
for (int j = 1; j <= n; ++j) {
if (d[j] > ds) {
tempDis = -1;
break;
}
if (d[j] < tempDis) {
tempDis = d[j];
}
tempAve += d[j] * 1.0 / n;
}
if (tempDis == -1)continue;
if (tempDis > ansDis) {
ansDis = tempDis;
ansAve = tempAve;
index = i;
}
else if (tempDis == ansDis && tempAve < ansAve) {
ansAve = tempAve;
index = i;
}
}
if (index == -1) printf("No Solution\n");
else printf("G%d\n%.1f %.1f\n", index - n, ansDis, ansAve);
return 0;
}
如果这篇文章对你有张帮助的话,可以用你高贵的小手给我点一个免费的赞吗
相信我，你也能变成光.
如果你有任何建议,或者是发现了我的错误,欢迎评论留言指出.