1. 题目到底在说什么千万别被“加油站”三个字带偏PTA 1072 Gas Station这道题光看标题很容易误会成“图论里的选址问题”但实际读完你会发现它更像一道“披着图论外衣的逻辑判断题”。题目背景是一个小区里要建加油站候选位置有若干个要求加油站到所有居民点的距离都不能超过一个给定的服务范围。我们要做的就是从这些候选位里挑出最佳的那个并输出它的编号、到居民点的最短距离以及到所有居民点的平均距离。听起来很简单对吧但真正的难点不在算法本身而在“最佳”的定义顺序上。我把原题要求翻译成人话按优先级排一下所有居民点都必须在加油站的“服务半径”内只要有一个居民点超了这个候选位直接淘汰。在所有能覆盖全部居民点的候选位中选“离最近居民点最远”的那个也就是让最近的那户人家也能尽量离加油站远一点避免打扰居民生活。如果最近距离一样再比较“到所有居民点的平均距离”平均距离更小的优先。平均距离还一样按编号从小到大选。这里最容易让人懵的是第2条。大多数人第一次读题都会默认“加油站应该离居民区越近越好”但题目偏偏反着来——它要求的是“最近距离最大化”。后面牛客网和PTA测试点不通过的问题九成以上都出在这个理解偏差上。顺带说一下输出格式如果候选位里面有合法解输出格式是编号 最短距离(保留一位小数) 平均距离(保留一位小数)。如果没有一个候选位能覆盖全部居民点就输出No Solution。注意平均距离的保留规则很坑它不是四舍五入而是保留一位小数并且题目明确说了要“四舍五入到0.1”但实现的时候很多人踩了浮点坑。提示这道题建议用一个结构体存候选位的编号、最短距离、平均距离最后统一排序或择优不要边算边直接更新最优解很容易因为浮点比较出问题。2. 建模思路与算法选型为什么是Dijkstra而不是Floyd这道题的图模型很直白居民点和候选加油站点都是图上的节点边就是道路权重就是道路长度。候选加油站的数量不超过10个这是题目给的范围后面选算法就靠它了居民点最多1000个。整个图最多有1000多个节点边数在题目给的范围内也不算夸张。既然候选加油站最多10个最朴素也最稳妥的做法就是对每个候选加油站跑一次单源最短路径Dijkstra得到它到所有居民点的最短距离然后逐个判断是否超服务范围最后按规则择优。总复杂度大约10次Dijkstra每次都跑在1000个节点级别的图上完全没压力。那为什么不用Floyd-Warshall理论上多源最短路一步到位但Floyd是N立方复杂度N是1000的话就是10亿级别运算在PTA的时间限制下大概率超时。就算勉强过了代码写起来也更绕完全没有必要。Dijkstra用堆优化的写法一次也就几十毫秒的级别10次也就几百毫秒稳得很。还有一个小细节节点编号怎么处理题目里居民点编号是1到N候选加油站编号是带字母G的比如G1、G2、G3。实现时要把加油站映射到居民点编号之后的空间里比如居民点占1到N加油站就从N1开始编号。这个映射很多教程里讲得不够清楚我后面会专门演示一段代码。另外输入里边的边是“双向道路”还是“单向道路”原题描述用的是roads一般是无向边也就是双向。但如果某道题变种成了有向边Dijkstra照样能跑不用改算法只是建图的时候注意加边的方向就行。这道题不用考虑负权边因为道路长度不可能是负的。注意建图时居民点编号也可能出现H开头之类的变体吗PTA原题不会但牛客网改编版曾经出现过用G代表加油站的固定格式前后保持一致就好。关键是编号映射要唯一别把G1和1当成同一个节点。3. 两个平台测试点不通过的根因分析不是算法错是题意错我在PTA和牛客网都提交过这道题前后卡了很长时间。最开始我以为是自己Dijkstra写挂了查来查去各种print大法都用了结果发现算法本身完全正确真正的坑全在“选最优”的规则理解和浮点输出上。这里我把两个平台上典型的WA原因逐条列出来。坑点一把“最近距离最大化”理解成了“平均距离最小化优先”这是最普遍的错法。很多人读完题凭直觉认为加油站就是要让所有居民都方便于是写排序规则时把平均距离作为首要条件。结果就是样例过得了但PTA第4、第5个测试点直接WA牛客网的第2个测试点也会挂。道理很简单样例里恰好只有一个合法候选位怎么做都对但测试数据一旦出现“两个候选位都合法、最近距离不同”的情况你的排序规则就决定成败。坑点二服务范围比较时用了带浮点的等号判断题目给的服务范围是整数道路距离也是整数那为什么会有浮点问题因为Dijkstra算出来的是整数距离的累加理论上不会出现小数。但如果你用的是double类型存距离并且在判断minDist range时直接比较其实不会出问题。真正出问题的是输出平均距离那一刻你用printf(%.1f, avg)由于浮点数精度比如3.25可能存成3.2499999printf的rounding规则就会把它打印成3.2而不是期望的3.3。解决办法有两个一是做四舍五入时手动加一个很小的epsilon二是用整数距离累加只在最后算平均值时转成浮点。最稳妥的写法是平均距离保留一位小数时用avg 1e-7再去格式化。这个细节看起来小但测试点里一旦有3.25这种精确到.25的边界值你就知道它多要命了。坑点三输出最短距离时没有遵守“服务范围内最大最近距离”的输出有些题解会用minDist表示“加油站到所有居民点的最短距离”然后输出它。这本身没错但要注意这个minDist必须是在“服务范围内全部覆盖”的前提下算出来的不是某个加油站所有最短距离里随便取一个最小的。也就是说只要有一个居民点超过服务范围这个候选位就不参与比较不输出任何值。有人会把超范围的点距离强制改成极大值然后继续参与排序这会导致本来不合法的点被误选。测试点里一定会安排“某个候选点超服务范围但另一个候选点合法”的情况用来验证你有没有在判断时直接淘汰掉不合法候选。每次提交前我都会问自己一句如果两个候选位最短距离相等平均距离也相等我的程序还稳定吗这里记住编号小的优先。如果你用排序实现排序规则里最后一个关键字必须是编号升序否则在极端测试下可能输出错误候选位。4. 核心代码实现一版能同时过PTA和牛客网的写法直接上一版我最终通过的完整实现。语言用C代码里注释写得比较详细便于对照前面的坑点。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; struct Node { int id; // 候选加油站编号1~M输出时对应Gid int minDist; // 到所有居民点的最短距离中的最小值 int sumDist; // 到所有居民点的距离之和 }; struct Edge { int to, weight; }; int n, m, k, range; // 居民点数、候选加油站数、边数、服务范围 vectorEdge graph[1100]; // 节点总数最多 n m这里取 1100 足够 // 把输入的 Gx 或数字编号转换成内部节点编号 int parseNode(const string s) { if (s[0] G) { return n stoi(s.substr(1)); } return stoi(s); } void dijkstra(int start, vectorint dist) { dist.assign(n m 2, INF); dist[start] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; for (auto e : graph[u]) { int v e.to; if (dist[v] d e.weight) { dist[v] d e.weight; pq.push({dist[v], v}); } } } } bool cmp(const Node a, const Node b) { if (a.minDist ! b.minDist) return a.minDist b.minDist; // 最近距离越大越好 if (a.sumDist ! b.sumDist) return a.sumDist b.sumDist; // 平均距离越小越好 return a.id b.id; // 编号小优先 } int main() { cin n m k range; for (int i 0; i k; i) { string a, b; int w; cin a b w; int u parseNode(a); int v parseNode(b); graph[u].push_back({v, w}); graph[v].push_back({u, w}); } vectorNode candidates; for (int i 1; i m; i) { int start n i; // 候选加油站的内部编号 vectorint dist; dijkstra(start, dist); bool valid true; int minDist INF; int sumDist 0; for (int j 1; j n; j) { if (dist[j] range) { valid false; break; } minDist min(minDist, dist[j]); sumDist dist[j]; } if (valid) { candidates.push_back({i, minDist, sumDist}); } } if (candidates.empty()) { printf(No Solution\n); return 0; } sort(candidates.begin(), candidates.end(), cmp); Node best candidates[0]; double avg (double)best.sumDist / n; printf(G%d\n%.1f %.1f\n, best.id, (double)best.minDist, avg 1e-7); return 0; }这个代码的核心思路分三步第一步解析节点编号把居民点和加油站统一到内部编号体系第二步对每个加油站跑Dijkstra同时判断合法性和统计距离信息第三步把所有合法候选位塞进vector排序后取第一个输出。其中比较函数cmp是整道题的灵魂。a.minDist b.minDist对应“最近距离越大越好”a.sumDist b.sumDist对应“平均距离越小越好”最后a.id b.id保证编号升序。如果你前面的排序规则写反了哪怕算法和建图全对也一定WA。还有一点需要说明sumDist / n得到的平均距离是浮点输出前加1e-7是为了避免浮点边界问题。我测试过某些输入下直接printf(%.1f, avg)会得到比期望小0.1的结果加上epsilon就能修正。提示这里printf(G%d\n%.1f %.1f\n, best.id, ...)的输出顺序要仔细对照题目。题目要求第一行输出编号第二行才是最短距离和平均距离格式是“最短距离 平均距离”不要写反了。5. 典型测试用例复盘为什么样例能过你却还是WA为了帮大家彻底搞懂题意我构造一组比样例更容易暴露问题的数据手动推演一遍。这组数据不是题目原题但完全贴合题目的坑点。假设有3个居民点2个候选加油站服务范围是10道路如下1号居民点和G1之间距离42号居民点和G1之间距离63号居民点和G1之间距离101号居民点和G2之间距离92号居民点和G2之间距离93号居民点和G2之间距离9先看G1到三个居民点的最短距离分别是4、6、10全在10以内合法。最短距离minDist 4距离和sumDist 20。再看G2到三个居民点的最短距离分别是9、9、9全在10以内合法。最短距离minDist 9距离和sumDist 27。按规则排序G2的minDist是9大于G1的4所以G2胜出。输出G2 9.0 9.0。运行我上面的代码结果就是它。但如果你的排序规则是“平均距离越小越优先”你会输出G1直接WA。这个例子说明题目要的不是“离所有居民最近”而是“在覆盖所有居民的情况下让最近的那个居民也离得尽量远”。这种选点策略更贴近规划场景——加油站建在居民区边缘而非正中央减少噪声和安全影响。想通这一点比多刷十道题都管用。再举一个测试点里容易出现的边界服务范围判断。假设G1到某居民点距离恰好等于range比如上面例子里3号居民点距离G1是10range也是10那算合法吗合法。dist[j] range是超范围等于range不算超。很多WA就是把大于号写成了大于等于等于时也被淘汰导致合法候选变少输出No Solution。注意比较服务范围时用用会把边界值误判为不合法。测试数据专门设计了这种边界用例等着粗心的人踩。6. 牛客网和PTA的差异同一道题注意这几个细节PTA和牛客网都收录了这道题但两边的测试点和输入输出格式在某些细节上有微妙差别。我在这两个平台上都AC了下面把差异点梳理一下免得你在一个平台过了换到另一个平台又莫名WA。第一输出时的换行和空格。PTA对行末空格和多余换行容忍度较高但牛客网很多时候要求严格。建议严格按照题面输出不要多打印空格。我上面给的printf格式就没有多余空格。第二牛客网的节点编号处理。居民点编号有时候会超过1000吗理论上不会但保险起见数组开大一点比如开到1100甚至更高避免段错误。PTA的测试数据相对温和但牛客网偶尔会出一些压力数据数组开小了容易RE。第三输入的边权可能重复。同一个道路可能存在多条记录但道路长度都取最后一次输入还是取最小按题意两个节点间可能存在多条路应该取最短的那条。不过Dijkstra本身就处理了“多条边取最短”的情况因为堆优化会不断松弛出最短路径所以不用额外去重。只要你在建图时把所有边都加进去Dijkstra自然选最短。第四牛客网出现过“加油站数量为0”的极端输入吗理论上不会因为候选加油站数量M至少为1否则题目没有意义。但代码里还是写一下空vector的判断避免野指针。实测下来只要排序规则对、浮点输出加了epsilon、服务范围边界用PTA和牛客网两个平台都能一次过。如果还WA检查一下parseNode是不是把G10解析成了n 10注意stoi(10)的结果是10不是把G后面的数字当作字符处理不然G10会被解析成n 49直接爆炸。7. 避坑清单我把所有能踩的坑都总结成了一份速查表写到最后把这道题从读题到AC整个过程中最容易踩的坑整理成一张表。刷题时可以在提交前对照自查能省不少时间。检查项正确做法错误做法排序优先级最近距离最大优先再比平均距离平均距离优先服务范围判断dist[j] range 则不合法用 导致边界误判浮点输出avg 1e-7 再 printf直接 printf 受精度影响编号映射G1 - n1G10 - n10把G后面的数按字符处理Dijkstra起点每个加油站跑一次对所有节点跑Floyd最终输出最短距离在前平均距离在后顺序写反无解输出精确输出 No Solution漏掉换行或拼写错误这里再多说一句浮点的问题。为什么avg 1e-7有效因为double类型在表示类似3.25这样的十进制小数时实际存储值可能是3.2499999999999996printf(%.1f)按照四舍五入规则会把这个值打印成3.2因为保留一位小数看第二位第二位是4。加上1e-7之后值变成3.250000099第二位小数是5四舍五入就正确打印成3.3了。这个操作在很多图论和计算几何题里都通用建议养成习惯。再有就是输出平均距离的时候除以的是居民点数量n不是节点总数nm。很多人把加油站到所有节点包括其他加油站的距离也加进了sumDist导致输出偏大。题目明确只要求“到所有居民点的平均距离”其他加油站不算。个人经验这道题完全可以不用排序遍历候选位时手工维护最优也行但排序的好处是代码逻辑一目了然检查规则时不容易漏掉“编号最小优先”这一条。我建议新手先用排序法写AC之后再尝试手工维护加深理解。8. 从这道题能带走的通用能力Gas Station这道题本身不复杂但它把“图论最短路径”和“多条件排序”结合得特别典型。刷完它你会发现很多题目都有类似的套路先跑最短路拿到基础数据再按照题目给定的复杂规则筛选和排序。只要规则理清楚代码写起来其实都是模板活。我个人觉得这道题最大的价值是训练“反向直觉”的读题能力。大部分人一看“加油站选址”立刻联想到“离居民越近越好”但题目偏要最大化最近距离。这种反直觉的规则在真实工程项目里也经常出现——你以为某个指标越高越好但需求文档里写的是“在满足A的前提下最小化B”。读懂这种隐含约束比闷头写算法重要得多。如果你准备参加算法竞赛或者机考建议把这道题的做法彻底吃透尤其是排序规则和浮点输出那两处能帮你避开一大半WA。就算以后不写图论题处理多条件排序、格式化输出这些基本功也是通用的。最后分享一个我自己的调试习惯每次WA之后我会构造一个“故意让两个候选位在最近距离相同、平均距离相同”的数据看输出是否按编号从小到大。如果这个用例都过不了那肯定是排序规则不完整。这个方法帮我抓住过好几次漏写id排序的错误你也可以试试。
