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，加油站就从N+1开始编号。这个映射很多教程里讲得不够清楚，我后面会专门演示一段代码。
另外，输入里边的边是“双向道路”还是“单向道路”？原题描述用的是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.2499999，printf的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，输出时对应G+id） int minDist; // 到所有居民点的最短距离中的最小值 int sumDist; // 到所有居民点的距离之和 }; struct Edge { int to, weight; }; int n, m, k, range; // 居民点数、候选加油站数、边数、服务范围 vector<Edge> 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, vector<int>& dist) { dist.assign(n + m + 2, INF); dist[start] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, 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}); } vector<Node> candidates; for (int i = 1; i <= m; ++i) { int start = n + i; // 候选加油站的内部编号 vector<int> 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之间距离4
- 2号居民点和G1之间距离6
- 3号居民点和G1之间距离10
- 1号居民点和G2之间距离9
- 2号居民点和G2之间距离9
- 3号居民点和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是10，range也是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 -> n+1，G10 -> n+10 | 把G后面的数按字符处理 |
| Dijkstra起点 | 每个加油站跑一次 | 对所有节点跑Floyd |
| 最终输出 | 最短距离在前，平均距离在后 | 顺序写反 |
| 无解输出 | 精确输出 No Solution | 漏掉换行或拼写错误 |
这里再多说一句浮点的问题。为什么avg + 1e-7有效？因为double类型在表示类似3.25这样的十进制小数时，实际存储值可能是3.2499999999999996，printf("%.1f")按照四舍五入规则，会把这个值打印成3.2，因为保留一位小数看第二位，第二位是4。加上1e-7之后，值变成3.250000099，第二位小数是5，四舍五入就正确打印成3.3了。这个操作在很多图论和计算几何题里都通用，建议养成习惯。
再有就是输出平均距离的时候，除以的是居民点数量n，不是节点总数n+m。很多人把加油站到所有节点（包括其他加油站）的距离也加进了sumDist，导致输出偏大。题目明确只要求“到所有居民点的平均距离”，其他加油站不算。
个人经验：这道题完全可以不用排序，遍历候选位时手工维护最优也行，但排序的好处是代码逻辑一目了然，检查规则时不容易漏掉“编号最小优先”这一条。我建议新手先用排序法写，AC之后再尝试手工维护，加深理解。
8. 从这道题能带走的通用能力
Gas Station这道题本身不复杂，但它把“图论最短路径”和“多条件排序”结合得特别典型。刷完它，你会发现很多题目都有类似的套路：先跑最短路拿到基础数据，再按照题目给定的复杂规则筛选和排序。只要规则理清楚，代码写起来其实都是模板活。
我个人觉得这道题最大的价值是训练“反向直觉”的读题能力。大部分人一看“加油站选址”，立刻联想到“离居民越近越好”，但题目偏要最大化最近距离。这种反直觉的规则在真实工程项目里也经常出现——你以为某个指标越高越好，但需求文档里写的是“在满足A的前提下最小化B”。读懂这种隐含约束，比闷头写算法重要得多。
如果你准备参加算法竞赛或者机考，建议把这道题的做法彻底吃透，尤其是排序规则和浮点输出那两处，能帮你避开一大半WA。就算以后不写图论题，处理多条件排序、格式化输出这些基本功也是通用的。
最后分享一个我自己的调试习惯：每次WA之后，我会构造一个“故意让两个候选位在最近距离相同、平均距离相同”的数据，看输出是否按编号从小到大。如果这个用例都过不了，那肯定是排序规则不完整。这个方法帮我抓住过好几次漏写id排序的错误，你也可以试试。
