PYTHON LESSON 124
例题精练：基站选址的最坏情况
拆解“最小化最大距离”题型：先 Floyd 求全源最短路，再逐点取最大值、全局取最小。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- Floyd 三重循环 for k → for i → for j
- worst[v] = max(dist[v]) 每个点的最坏情况
- 严格小于才更新答案，编号小的自动优先
01 · 核心概念
Floyd 全源最短路 + 最小化最大值（minimax）
Floyd 全源最短路 + 最小化最大值（minimax）：“最坏情况最好”要读两遍：对每个候选村庄，它的代价是“到最远村庄的最短距离”（最坏情况）；然后在所有村庄里挑这个代价最小的（最好）。把两层意思拆开，代码结构就出来了：外层挑村，内层算最远。
GESP Python 8 级 · 多源最短路（Floyd）GESP Python 8 级 · 时间与空间复杂度分析有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
Floyd 三重循环 for k → for i → for j先准确读出这条写法的结构与作用。
worst[v] = max(dist[v]) 每个点的最坏情况换一组最小数据，手工推演一次结果。
严格小于才更新答案，编号小的自动优先再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 例题精练：基站选址（题库 py-base-station 同款思路）
# 选一个村庄建基站，使它到其他村庄最短距离的最大值尽量小
import sys
def main():
data = sys.stdin.buffer.read().split()
pos = 0
n = int(data[pos]); m = int(data[pos + 1]); pos += 2
INF = float("inf")
dist = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dist[i][i] = 0
for _ in range(m):
a = int(data[pos]); b = int(data[pos + 1]); w = int(data[pos + 2]); pos += 3
if w < dist[a][b]: # 可能有重边，只留最短的
dist[a][b] = w
dist[b][a] = w
# Floyd：三重循环求任意两点最短路
for k in range(1, n + 1):
dk = dist[k]
for i in range(1, n + 1):
di = dist[i]
if di[k] == INF:
continue # i 到不了 k，这轮跳过
via = di[k]
for j in range(1, n + 1):
nd = via + dk[j]
if nd < di[j]:
di[j] = nd
# 每个村庄的“最坏情况”：到其他村庄的最大距离
best_v, best_worst = -1, INF
for v in range(1, n + 1):
cur = max(dist[v][1:])
if cur < best_worst: # 严格小于，编号小的自动优先
best_worst = cur
best_v = v
print(best_v)
print(best_worst)
main()2 5
假设输入为：第一行 4 5（4 村 5 路），随后 5 行依次是 1 2 2 / 1 3 3 / 2 3 4 / 2 4 5 / 3 4 6。输出两行：基站建在 2 号村，最坏距离 5。
04 · 逐步理解
每一步只解决一个问题
- 01
第一步：读题，读懂 minimax
“最坏情况最好”要读两遍：对每个候选村庄，它的代价是“到最远村庄的最短距离”（最坏情况）；然后在所有村庄里挑这个代价最小的（最好）。把两层意思拆开，代码结构就出来了：外层挑村，内层算最远。
# 外层：枚举建基站的村 v # 内层：max(dist[v]) 是 v 的最坏情况 - 02
第二步：看数据范围选算法
n ≤ 150，Floyd 的 O(n³) 约 3.4×10^6 次操作，Python 也能秒过；而且这题要的是“任意两点”的距离表，Floyd 一次算全最划算。若 n 到 10^4 就得改成跑 n 次堆优化 Dijkstra——先估算再动手的老规矩不变。
# n ≤ 150 → O(n^3) ≈ 3.4×10^6，Floyd 可行 - 03
第三步：建图的两个细节
邻接矩阵初始化：对角线 0、其余 INF。输入可能有重边（两个村之间给了两条路），只保留最短的那条——不重边判断就会用更长的边算距离，答案直接偏大，这是竞赛输入常埋的坑。
if w < dist[a][b]: dist[a][b] = w dist[b][a] = w - 04
第四步：Floyd 主体与一个小优化
三重循环 k→i→j 照模板写，k 必须最外层。顺手加一个优化：di[k] == INF 时整轮跳过——i 根本到不了中转站 k，内层循环纯属浪费。稀疏图上这行 continue 能省下可观的时间。
if di[k] == INF: continue - 05
第五步：扫描答案，编号小的优先
逐行取 max 得到每个村庄的最坏情况，再取其中的最小值。比较用严格小于 cur < best_worst：打平时不更新，先扫到的编号小者自动留下——正好满足题目“并列取编号最小”的要求，不用额外写 tie-break。
if cur < best_worst: best_worst = cur best_v = v - 06
变体与复盘
把“最远村庄距离最小”改成“到所有村庄总距离最小”，就得到另一个经典考点（图的重心）：只需把 max 换成 sum。先全源最短路、再按行统计，是所有选址类题目的通用骨架。
cur = sum(dist[v][1:]) # 变体：总距离最小
05 · 练习与检验
自己写出来，才算真正学会
- 1运行选址官，核对建在 2 号村、最坏距离 5
- 2手算 1 号村的最坏距离为什么是 7
- 3把 3-4 的路改成 1，看选址是否改变
- 4解释这题为什么选 Floyd 而不是 4 次 Dijkstra
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
完成检查