松弛与最短路上界
约 55 分钟
松弛与最短路上界
先别猜算法，先把问题说清楚
今天只解决一个具体任务：手工执行一轮边松弛并找出仍可能改进的顶点。。上一节《网格图与隐式邻接》已经产出一个可检查的状态或边界；今天不要清零重来，要把它带进《松弛与最短路上界》。 你先复述输入是什么、输出必须唯一满足什么、哪些输入合法、出现并列或无解怎样返回、能否修改输入、下标从零还是从一开始。若这些话写不完整，样例跑对也不能证明程序做的是同一道题。本节案例编号是 cs-08-leetcode/u11/l01/松弛与最短路上界/contract，后续代码、证明和测试都引用同一份契约。
为什么在这里学习它
本章要解决的是：用松弛维护距离上界，用不同数据结构适配非负边、负边、全源和动态区间查询。。本节不是孤立模板，它承担的连接是：松弛是共同核心，下一课利用非负边贪心确定顶点。 我们会先保留一个显然正确但可能很慢的方案，再圈出重复工作；只有能指出被删掉的工作为何不影响答案，优化才有依据。面试时真正有价值的不是迅速喊出算法名，而是让对方看到你怎样从限制推出模型。
核心不变量和复杂度必须单独写
把这句话拆成三层。第一层是状态语义：变量、区间、栈、队列或 dp 项究竟代表哪一段已经完成的工作。第二层是保持性：本轮读入一个新元素后，怎样更新仍使语义成立。第三层是终止性：循环或递归结束时，这个语义为什么恰好推出题目要求的答案。复杂度要从元素进入、退出、比较或转移的次数累加，不能凭印象写 O(n)。
跟我从暴力基线走到优化
先为“手工执行一轮边松弛并找出仍可能改进的顶点。”写一个覆盖全部候选的基线，并用两三个最小输入说明它没有漏解。接着在纸上标出哪些区间、比较或子问题被反复计算。现在引入本节状态：每处理一步，都用一句话重述“已经完成什么、仍未知什么”。若要移动指针、弹栈、丢弃搜索区间或覆盖 dp，必须证明被丢掉的候选不可能成为更优答案。最后才写代码，并把每个分支对应回契约中的一种情况。
课堂上至少手推三组：普通输入用于看主流程；最小或空输入用于看初始化；带重复、并列、负数、极值或不可达状态的输入用于看边界。每轮写出关键状态，而不是只写最后答案。这样当程序错时，你能判断错误来自规格、模型、不变量、实现还是测试，而不是盲目换模板。（推导锚：cs-08-leetcode/u11/l01/松弛与最短路上界/trace。）
一个完整例题怎样讲给人听
围绕“手工执行一轮边松弛并找出仍可能改进的顶点。”，先给一个小输入，逐步列出状态表或指针位置；再解释为什么下一步只有当前动作安全。随后把规模扩大到约束上界，按“状态数 × 每状态工作量”核算时间，并把数组、哈希、递归栈或队列占用逐项计入空间。若存在两种方案，要比较它们依赖的前提，而不是一律选择渐近阶更低者：排序会改变顺序，哈希有额外空间，递归有栈深，位运算受数值范围限制。
今天最重要的失败边界
请故意构造这个失败：不可达距离参与加法会溢出；边权和路径长度需使用足够宽整数。。先预测错误程序第一次在哪一轮偏离，再运行最小反例验证。只说“注意边界”不给分；必须写出输入、错误状态、错误输出和违反的契约。若修复需要新增特判，反问能否改写初始化或区间语义，让空输入、首尾元素和普通输入走同一条逻辑。（反例锚：cs-08-leetcode/u11/l01/松弛与最短路上界/counterexample。）
在线编程题怎样严格验收
本课绑定的代码题使用真实 Python 3 标准输入输出，不是伪代码。先在编辑器中写可运行基线，再提交优化版。基础任务至少六组、标准任务至少八组、挑战任务至少十组测试，覆盖普通、最小、空或单元素、重复/并列、极值、不可达以及复杂度压力。判题通过只证明这些可观察输入输出满足契约；你还要在题解里说明不变量、复杂度和未覆盖风险。
随课四题怎么做
单选题检查哪一种推理链成立；多选题同时验收规格、不变量、复杂度和反例，漏选或多选均错；状态计算题要求把简化操作次数算出来并说明模型；证明题按十分量表评分：契约与基线2分，不变量与保持性3分，终止和正确性2分，复杂度1分，失败边界与测试2分。只贴最终代码、只写算法名或只报复杂度不能证明已经学会。
下课前闭卷交付
不看正文，用五分钟完成一页题解：一句话契约；一个暴力基线；状态语义；初始化—保持—终止证明；时间和空间来源；“不可达距离参与加法会溢出；边权和路径长度需使用足够宽整数。”的最小反例；六到十组测试分类；最后口述如何完成“手工执行一轮边松弛并找出仍可能改进的顶点。”。下一节《Dijkstra 的确定性》会直接使用今天留下的状态、反例或复杂度结论。 如果其中任何一项只能靠背诵恢复，就回到对应代码行重新手推。（闭环锚：cs-08-leetcode/u11/l01/松弛与最短路上界/handoff。）
Practice
本课练习
先独立作答再提交；编程题会在隔离沙箱中真实编译、运行并对拍。
在《松弛与最短路上界》中，若每个元素恰好完成一次主处理，输入规模 n=74 时主处理次数是多少？ 先写采用的计数模型，并说明它为何只是一种上界估算。
本题专题为《松弛与最短路上界》。围绕“手工执行一轮边松弛并找出仍可能改进的顶点。”写完整题解：契约、暴力基线、状态语义、初始化—保持—终止证明、时间/空间来源、针对“不可达距离参与加法会溢出；边权和路径长度需使用足够宽整数。”的最小反例和分层测试。只贴代码不得分。
按给定边序更新距离并输出结果。 输入：第一行n、m、src，随后m条按给定顺序的有向边u v w。 输出：只执行一轮顺序松弛，输出距离，未达为INF。 约束：1≤n≤100000。 使用 Python 3 从标准输入读取，向标准输出写出唯一规定结果；不得读取文件或网络。 使用 Python 3 标准输入输出；不得使用第三方包。必须覆盖题面边界，不能只针对样例。
支持区间修改与区间查询。 输入：第一行n、q，第二行数组，随后ADD l r v或SUM l r。 输出：每条SUM输出闭区间和。 约束：1≤n,q≤200000。 使用 Python 3 从标准输入读取，向标准输出写出唯一规定结果；不得读取文件或网络。 使用 Python 3 标准输入输出；不得使用第三方包。必须覆盖题面边界，不能只针对样例。
试卷专题《松弛与最短路上界》要求为“手工执行一轮边松弛并找出仍可能改进的顶点。”提交契约、基线、dist[v] 始终是已发现路径的最小长度上界，松弛只会减小它。 的正确性证明、复杂度、针对“不可达距离参与加法会溢出；边权和路径长度需使用足够宽整数。”的反例和测试计划。