PAT A1072 Gas Station

news/2024/10/30 9:36:12/

1072 Gas Station

分数 30

作者 CHEN, Yue

单位 浙江大学

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 DS​, 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

  * 首先建图,居民所从1开始编号,加油站从N+1开始编号,如果是加油站,
 * 则将顶点创建为编号加N,与居民点区分开;
 *
 * 此后就是一个Dijkstra模板,我使用的是堆优化的Dijkstra算法;
 * 详看代码:

/*** 首先建图,居民所从1开始编号,加油站从N+1开始编号,如果是加油站,* 则将顶点创建为编号加N,与居民点区分开;* * 此后就是一个Dijkstra模板,我使用的是堆优化的Dijkstra算法;* 详看代码:
*/#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>using namespace std;typedef pair<double, double> PDD;
typedef pair<int, int> PII;const int N = 1010, M = 2*N, INF = 1e9;
vector<PII> Adj[M]; //要建立居民所和加油站,所以要开二倍N的空间
int d[M];
bool hs[M];
int Nv, Ne, m, T;void Read()
{cin >> Nv >> m >> Ne >> T;for(int i=0; i<Ne; ++i){string a, b;int u, v, w;cin >> a >> b >> w;//如果是加油站,则将顶点创建为编号加N,与居民点区分开if(!isdigit(a[0]))   u = stoi(a.substr(1)) + N; else u = stoi(a);if(!isdigit(b[0]))   v = stoi(b.substr(1)) + N;else v = stoi(b);Adj[u].push_back({v, w});Adj[v].push_back({u, w});}
}PDD Dijkstra(int st)
{//注意别写成了N,最开始就写成了N,调试了半天fill(hs, hs+M, 0);fill(d, d+M, INF);priority_queue<PII, vector<PII>, greater<PII>> pq;pq.push({0, st}); d[st] = 0;while(pq.size()){PII fs = pq.top();pq.pop();int u = fs.second;hs[u] = 0;for(auto ele : Adj[u]){int v = ele.first, w = ele.second;if(d[u] + w < d[v]) {d[v] = d[u] + w;if(hs[v] == 0){pq.push({d[v], v});hs[v] = 1;}}}}int MIN = INF, MAX = -1;double avg = 0;for(int i=1; i<=Nv; ++i){MIN = min(MIN, d[i]);MAX = max(MAX, d[i]);avg += d[i];}//最大距离超过了服务范围,则该点不能设为加油点if(MAX > T) MIN = -1;//返回最小距离以及平均距离return {MIN, avg/Nv};
}int main()
{Read();int idx = -1;PDD res = {0, INF};for(int i=1; i<=m; ++i){int u = i + N;PDD tm = Dijkstra(u);//最短距离更大if(tm.first > res.first)    {res = tm;idx = i;}//最短距离相同的情况选择平均距离更短的点else if(tm.first == res.first && tm.second < res.second){res = tm;idx = i;}}//没有解的情况if(idx == -1)   puts("No Solution");else {printf("G%d\n", idx);printf("%.1f %.1f\n", res.first, res.second);}return 0;
}


http://www.ppmy.cn/news/271563.html

相关文章

【利用AI让知识体系化】前端安全攻防知识点

文章目录 1. 前言1.1 前端安全攻防的意义1.2 概述前端安全攻防的范畴和流程 2. 攻击技术2.1 XSS攻击2.1.1 原理和类型2.1.2 预防和防御 2.2 CSRF攻击2.2.1 原理和类型2.2.2 预防和防御 3. 代码层次3.1 JavaScript代码安全3.1.1 客户端JavaScript安全3.1.2 服务器端JavaScript安…

【MySQL数据库 | 番外篇】 聚合函数

前言&#xff1a; 聚合函数是分组查询中一个重要的组成部分&#xff0c;想要利用分组查询&#xff0c;就要对聚合函数有不错的掌握&#xff0c;因此我们在这里开一篇番外&#xff0c;讲解SQL语法中的聚合函数 聚合函数&#xff1a; 聚合函数是SQL中一种特殊的函数&#xff0c;…

final finally 和 finalize的区别

final、finally和finalize都是Java中的关键字&#xff0c;但它们的含义和用途却不同。 final 表示不可变&#xff0c;用于修饰类、方法和变量。 finally 表示无论如何都会执行的代码块&#xff0c;用于清理资源和恢复现场。 finalize 是Object类的一个方法&#xff0c;用于在…

【Java】Java核心要点总结:58

文章目录 1. java中 怎么确保一个集合不能被修改2. 队列和栈是什么 有什么区别3. Java8开始的ConcurrentHashMap为什么舍弃了分段锁4. ConcurrentHashMap 和 Hashtable有什么区别5. ReadWriteLock和StampeLock 1. java中 怎么确保一个集合不能被修改 Java 中可以使用 Collectio…

vue3开发web网页版免费ChatGPT

Vue3和TypeScript是目前非常流行的前端开发技术&#xff0c;它们的结合可以让我们更加高效地进行Web网页开发。本文将介绍Vue3和TypeScript的基本概念以及如何使用它们进行Web网页开发。 在浏览器中访问 https://shdily.com 就可以看到我们的Web网页了。 Vue3简介 Vue.js是一…

有了智能共享取餐柜,外卖也能吃出科技感

随着互联网和移动支付方式的普及&#xff0c;越来越多的黑科技逐渐出现在了大众视野中&#xff0c;比如智能家居&#xff0c;商用智能硬件&#xff0c;人工智能等&#xff0c;都是热议话题。而智能取餐柜解决了餐饮行业很普遍的几个痛点&#xff0c;在很大程度上缓解了吃饭难、…

ct值在哪里看_【行情】肇庆CT室硫酸钡施工报价

【行情】肇庆CT室硫酸钡施工报价 手术室净化器的无菌标准是什么&#xff1f;相信这是很多朋友心中的疑惑&#xff0c;所以我们的小编就请教了相关的专业人士并给大家整理了一下&#xff0c;下面我们就一起来看看这方面的介绍&#xff0c;相信能够让大家很好的认识这一点。&…

设计师:行业内设计师从出图到收费流程(设计收费标准、客户与设计师洽谈、设计师现场测量、设计师提供报价、设计图纸内容、签订合同、现场交底)之详细攻略

设计师:行业内设计师从出图到收费流程(设计收费标准、客户与设计师洽谈、设计师现场测量、设计师提供报价、设计图纸内容、签订合同、现场交底)之详细攻略 目录 行业内设计师从出图到收费流程 设计收费标准 1、客户与设计师洽谈