# 题解：加密数据包与网络清空

Codex（GPT-6）：应用非负权增量最短路，利用补齐规格中的阈值限制截断距离，给出逻辑边计数、清空维护与复杂度证明。

## 只保留阈值以内的距离

记 $d_v=\min(\operatorname{dist}(1,v),T+1)$ ，把 $T+1$ 作为统一的不可用距离。权值非负，超过 $T$ 的路径再追加边也不会回到阈值内，因此这种截断不影响是否清空的判断。

初始图读完后计算这些距离，但不执行清空。每加入一条有向弧 $(u,v,x)$ ，若 $d_u+x<d_v$ ，改进 $d_v$ 并加入最小堆。不断弹出当前有效距离，松弛其出弧；丢弃与当前距离不符的旧堆项。双向逻辑边加入两条弧，但逻辑边总数只加一。

## 为什么只传播改进就足够

插入前的距离已经正确。插入后，任何更短的路径都必须使用新弧，其第一次使用新弧时会产生一次端点松弛，之后按已有弧传播。每个被写入的有限距离都对应一条真实路径，所以不会低估最短距离。

传播结束时，每条弧都满足截断后的松弛不等式。沿任意路径逐边归纳，标签不会大于该路径长度或 $T+1$ .结合真实路径给出的反向不等式，标签就是截断后的最短距离。因此检查 $d_n\le T$ 恰好对应题目条件。

零权边和零权环也成立：只有严格改进才入堆，不会因等长环重复传播。非负权保证一次传播中的有效出堆顺序具有 Dijkstra 性质。

## 解密和清空

用 64 位整数计算 $(b+3)(c+37)$ ，先取模，再对每个字段异或。不得先把加密值当作顶点编号使用。

另设当前逻辑边数量 $e$ ，初始为 $m$ ；每包加一。清空时令 $b\gets b+e$ 、$e\gets0$ ，并删除所有弧。初始边和双向边的计数都由这个独立计数器处理。

清空只访问本轮实际用过的邻接表头和实际达到过的距离项。恢复源点距离为零，其他达到过的点恢复为 $T+1$ .不能每次清空都扫描全部顶点，否则反复加入一条直达边会导致 $O(nk)$ 的额外工作。

## 复杂度与取舍

设整个输入出现的有向弧总数为 $A\le2(m+k)$ .在相邻两次清空之间，一个顶点的距离最多从 $T+1$ 严格下降 $T+1$ 次。因此一条存活弧被其起点有效出堆扫描的次数至多 $T+1$ ；每条输入弧只属于一个这样的周期。

堆操作和弧扫描合计 $O(A(T+1))$ 次，时间为 $O(n+A(T+1)\log(n+A))$ .每次传播是非负权 Dijkstra，单条弧在这一轮至多产生一个入堆候选，所以空间为 $O(n+A)$ .累计清空开销线性于实际使用过的点、弧和周期数，已包含在上述界中。

逐包从头运行 Dijkstra 适合作为小规模核验，但可能重复访问几乎相同的图 $k$ 次。当前 $T\le100$ 保证增量算法的下降次数界；若放宽该阈值，必须重新评估复杂度，不能直接声称同样高效。

见[标准程序](std.cpp)、[测试说明](tests/README.md)和[性能记录](../../../docs/benchmark-R37.json)。