field noteENTRY / 010

Personal Field Archive / Received 2026.09.27

Dijkstra｜LeetCode 第一轮复盘

通过七道路径问题，复盘状态定义、路径聚合、优化方向、松弛操作与优先队列之间的稳定关系。

Logged: 2026.09.27
Filed under: 算法 / LeetCode / 图 / Dijkstra / 最短路径 / Python
Reading time: 14 min read
Series: Algorithm Field Notes / 08

章节状态：Dijkstra 当前计划 7 题第一轮已全部完成。题：743、1514、1631、1976、787、1368、778。已经从“标准 shortest path”推进到能够识别 Dijkstra 中的可变部分：state、best[state]、path aggregation、optimization direction、Priority Queue 方向，以及在最优值之外维护额外信息。当前最需要巩固的不是背模板，而是看到新题后能否先定义 best[state] 的语义，再自行推出 initialization、relaxation 和 heap。

一、题目清单

顺序	LeetCode	题目	核心训练	第一轮情况
1	743	Network Delay Time	标准 Dijkstra、Min Heap、stale entry	已完成
2	1514	Path with Maximum Probability	修改“最优”的定义、Max Heap	已完成
3	1631	Path With Minimum Effort	Grid + Dijkstra、minimax path	已完成
4	1976	Number of Ways to Arrive at Destination	Dijkstra + shortest path counting	已完成
5	787	Cheapest Flights Within K Stops	`node` 不足以描述完整 state、constraint 进入 state	已完成
6	1368	Minimum Cost to Make at Least One Valid Path in a Grid	0/1 edge weight、0-1 BFS	已完成
7	778	Swim in Rising Water	minimax shortest path	已完成

二、当前掌握情况

标准 Dijkstra 的基本结构已经建立。743 中完成了从“每轮扫描所有未处理节点找 minimum cost”到使用 Priority Queue / Min Heap 的转换，并理解了 dist 与 heap 的职责不同：dist[node] 保存当前 authoritative best value，heap 保存等待处理的 candidate states。

1514 开始能够把 Dijkstra 从“最短距离模板”抽象出来：path value 不一定通过加法得到，也不一定越小越好。1514 的 path value 是 probability，一条 path 内使用乘法累计，不同 paths 之间选择 maximum probability，因此 start identity、relaxation direction、Priority Queue direction 都随之改变。

1631 是目前最重要的一次迁移。最初倾向于先枚举 start → end 的所有 paths，再计算每条 path 的 effort 并比较；随后建立了以 state 为中心的思维：不保存所有完整 paths，而是维护“从 start 到当前 cell 的 best information”。本题一条 path 内取 MAX，不同 paths 之间取 MIN，即 minimize the maximum edge weight。

1976 在标准 shortest-distance Dijkstra 上增加了 ways[node]，开始理解 Dijkstra 不仅能维护 optimal value，也可以在 relaxation 时同步维护与 optimal solution 有关的额外信息。关键规则是：发现更短路径时替换 ways；发现同样短的路径时累加 ways。

787 进一步推进到 state design：认识到当 constraint 会改变未来合法选择时，node 本身不足以描述 state；需要使用 (node, flights_used)，并用二维 prices[node][flights_used] 保存对应 state 的 minimum price。目前最需要继续巩固的迁移能力是：

先定义 best[state]，再写代码；
区分 edge value、current path value、candidate value 和 best value；
区分“一条 path 内如何 aggregation”和“不同 paths 之间如何 optimization”；
不把 +、Min Heap、start = 0 当成 Dijkstra 固定规则；
明确 heap 与 best table 各自承担的职责；
当题目要求额外信息时，判断它应该如何随着 relaxation 替换或累加。

三、Dijkstra 的核心原则

1. Dijkstra 的核心不是“把 edge weights 相加”

前三道变体最重要的对照：

743:
path value = SUM
new_distance = current_distance + edge_weight

1514:
path value = PRODUCT
new_probability = current_probability * edge_probability

1631:
path value = MAX
new_effort = max(current_effort, edge_weight)

因此，Dijkstra 本身并不规定 path value 必须怎样计算。题目先定义“一个完整 path 的价值”，算法再维护从 start 到每个 state 的 best value。

更抽象地：

new_value = combine(current_value, edge_value)

if new_value is better than best[neighbor]:
    best[neighbor] = new_value

真正会随题目改变的是：

combine 是什么？
better 是什么？

2. 先定义 `best[state]` 的语义

做 Dijkstra 题时，最先回答的不是“heap 怎么写”，而是：

best[state] 到底表示什么？

四道题分别是：

743:
dist[node]
= start → node 的 minimum distance

1514:
probability[node]
= start → node 的 maximum probability

1631:
effort[r][c]
= start → (r,c) 的 minimum path effort

1976:
dist[node]
= 0 → node 的 minimum distance

ways[node]
= 达到 dist[node] 这个 minimum distance 的 path 数量

一旦这个语义定义清楚，initialization、relaxation 和 Priority Queue direction 通常都能从它推出来。

3. 区分 path 内部 aggregation 和 paths 之间 optimization

1631 最明显地暴露了这个区别。

一条 path：

edge weights = [2, 5, 3]

它的 effort 是：

max(2, 5, 3) = 5

这是 path 内部的 aggregation rule：MAX。

如果到同一个 cell 有三条 paths：

Path A effort = 8
Path B effort = 5
Path C effort = 6

则：

effort[cell] = min(8, 5, 6) = 5

这是 不同 paths 之间的 optimization rule：MIN。

所以 1631 是：

path 内：MAX
paths 间：MIN

不能因为 path 内部要取 MAX，就把未知 effort[cell] 初始化成 -inf。effort[cell] 保存的是不同 paths 之间的 best value，因此未知状态应初始化成 inf，这样第一次 candidate 才能通过：

if new_effort < effort[neighbor]:

4. Initialization 不是固定模板

Initialization 要从 path definition 和 optimization direction 推导。

题目	Path aggregation	Optimization	Start	未到达状态
743	`+`	MIN	`0`	`inf`
1514	`*`	MAX	`1.0`	`0.0`
1631	`max`	MIN	`0`	`inf`
1976 `dist`	`+`	MIN	`0`	`inf`
1976 `ways`	counting	—	`1`	`0`

1514 中：

1 × p = p

所以 start probability 是 1.0。

1976 中：

ways[0] = 1

表示从起点到自己存在 1 条 empty path。这个 1 是 path counting 向后传播的 seed；如果写成 0，所有后续 ways 都会保持为 0。

5. Priority Queue 与 `best` table 不能互相替代

这在 1514 的 Heap 版本中曾经混淆。

best table
    ↓
“目前从 start 到这个 state 的最好结果是多少？”

Priority Queue
    ↓
“所有等待处理的 candidate states 中，下一步优先处理谁？”

例如 743：

dist[node] → authoritative best-known distance
heap       → candidate (distance, node)

1514：

probability[node] → authoritative best-known probability
heap              → candidate (-probability, node)

1631：

effort[r][c] → authoritative best-known effort
heap         → candidate (effort, r, c)

Heap 中允许存在同一个 state 的多个 candidate，因此需要 stale entry check。

6. Stale entry 是 Lazy Deletion 的结果

假设某个 node 先被发现：

distance = 8

heap 中加入：

(8, node)

后来又发现：

distance = 5

于是：

dist[node] = 5

并加入：

(5, node)

旧的 (8, node) 不需要从 heap 中主动删除。之后 pop 出来时：

if current_dist > dist[node]:
    continue

即可跳过。

三题对应：

# 743
if current_dist > dist[node]:
    continue

# 1514
if current_prob < probability[node]:
    continue

# 1631
if current_effort > effort[r][c]:
    continue

判断方向取决于“better”的方向。

四、Dijkstra 的不变量与变数

四道题放在一起后，可以把 Dijkstra 拆成“不变骨架”和“题目决定的变数”。

不变骨架

best[start] = identity
push start into priority_queue

while priority_queue:
    current_value, state = pop_best()

    if current candidate is stale:
        continue

    for neighbor in neighbors:
        edge_value = ...

        new_value = combine(
            current_value,
            edge_value
        )

        if new_value is better than best[neighbor]:
            best[neighbor] = new_value
            push improved candidate

题目决定的变数

问题	743	1514	1631	1976
state	`node`	`node`	`(r,c)`	`node`
edge value	weight	probability	height difference	travel time
best	min distance	max probability	min effort	min distance
combine	`+`	`*`	`max`	`+`
better	`<`	`>`	`<`	`<`
start identity	`0`	`1`	`0`	`0`
PQ direction	Min	Max	Min	Min
extra state	—	—	—	`ways[node]`

做新的 Dijkstra 题时，应先回答：

state 是什么？
edge value 是什么？
best[state] 表示什么？
combine(current, edge) 是什么？
“better” 是 < 还是 >？
start identity 是什么？
未到达状态应该是什么？
Priority Queue 应该 min-first 还是 max-first？
是否还需要维护与 optimal solution 有关的额外信息？

五、重点题复盘

743. Network Delay Time

题目建模

times 是 directed weighted edge list：

[u, v, w]
= u --w--> v

需要求：

从 k 到所有 reachable nodes 的 shortest distance，再取这些 shortest distances 的最大值。

不是求 graph 中的 longest path。

Graph representation

graph = {}

for u, v, w in times:
    if u not in graph:
        graph[u] = []

    graph[u].append((v, w))

node 编号是：

1, 2, ..., n

因此：

dist = {
    node: float("inf")
    for node in range(1, n + 1)
}

dist[k] = 0

第一阶段：不用 Heap

最初使用：

find_lowest_cost_node(...)

每轮扫描所有未处理 nodes，找到 minimum cost 的 node。

这个版本逻辑上是 Dijkstra，但每轮选择 minimum node 需要 O(V) scan，因此整体会有 O(V²) 的部分。

Heap 优化

Priority Queue 的作用不是“避免比较”，而是：

增量维护 candidate ordering，使下一次 minimum candidate 不需要重新扫描所有 nodes。

核心：

heap = [(0, k)]

while heap:
    current_dist, node = heapq.heappop(heap)

    if current_dist > dist[node]:
        continue

    for neighbor, weight in graph.get(node, []):
        new_dist = current_dist + weight

        if new_dist < dist[neighbor]:
            dist[neighbor] = new_dist
            heapq.heappush(heap, (new_dist, neighbor))

最终：

max_dist = max(dist.values())

return -1 if max_dist == float("inf") else max_dist

第一轮暴露的问题

graph[node] 是 list，不能使用 .items()；
helper function 的 scope / self 容易混淆；
dist[k] 必须为 0；
relaxation 更新的是 neighbor；
graph 不一定包含没有 outgoing edge 的 node，因此使用 graph.get(node, [])；
Heap 中可以有 stale candidates，需要 Lazy Deletion。

1514. Path with Maximum Probability

最大变化：重新定义“最好”

这题不是 minimum distance，而是 maximum probability。

path 内：
probabilities 相乘

paths 间：
取 maximum

所以：

new_prob = current_prob * edge_prob

if new_prob > probability[neighbor]:
    probability[neighbor] = new_prob

Initialization

nodes 编号：

0, 1, ..., n - 1

因此：

probability = [0.0] * n
probability[start_node] = 1.0

start 是 1.0，因为：

1 × p = p

而不是沿用 743 的 0。

Graph construction

edges[i] 与 succProb[i] 一一对应：

for (u, v), prob in zip(edges, succProb):

并且是 undirected：

graph[u].append((v, prob))
graph[v].append((u, prob))

Max Heap

Python heapq 是 Min Heap，因此使用负数：

heap = [(-1.0, start_node)]

例如：

actual probabilities:
0.9, 0.6

heap values:
-0.9, -0.6

Min Heap 先取 -0.9，也就是实际 probability 最大的 0.9。

neg_prob, node = heapq.heappop(heap)
current_prob = -neg_prob

stale check：

if current_prob < probability[node]:
    continue

第一轮暴露的问题

把 743 的 start = 0 直接搬过来，没有先考虑 multiplication identity；
relaxation 一开始比较 new_prob > old_prob，而不是 new_prob > probability[neighbor]；
更新对象一开始写成 current node，而不是 neighbor；
graph construction 一开始把 edges 和 succProb 做 nested loop，而不是 zip；
从普通版本转 Heap 时，一度把 heap 当成可以替代 probability；
忘记 probability[neighbor] = new_prob，只把 candidate push 进 heap。

核心修正

Relaxation 永远应该问：

“通过 current 到达 neighbor 得到的 candidate，是否比目前 best[neighbor] 更好？”

而不是：

“candidate 是否比 current 更好？”

1631. Path With Minimum Effort

最初思路

最初倾向于：

找到 start → end 的所有 paths
→ 对每条 path 计算 effort
→ 最后比较所有 path

这个目标定义没有错：

每条 path effort
= path 上最大的 adjacent height difference

answer
= 所有 paths 的 effort 中最小的

即：

min over paths (max edge weight on path)

问题是不能实际枚举所有完整 paths。

Dijkstra 的 state compression

改为以 cell 为中心：

effort[r][c]
= 从 start 到 (r,c) 的所有已发现 paths 中
  minimum path effort

不是保存所有 paths，而是把它们压缩成一个 best value。

Edge weight

对于相邻 cells：

edge_weight = abs(
    heights[nr][nc] - heights[r][c]
)

它只描述当前这一小步有多陡。

不要把：

edge_weight

和：

effort[neighbor]

混为一谈。

Path aggregation

假设：

current_effort = 7
edge_weight = 4

新的完整 path effort 不是：

7 + 4 = 11

而是：

new_effort = max(7, 4)
           = 7

因为之前已经经历过 difference 7，新走一个 difference 4 的 edge 不会让整条 path 的 maximum 降低或累加。

Relaxation

if new_effort < effort[nr][nc]:
    effort[nr][nc] = new_effort
    heapq.heappush(
        heap,
        (new_effort, nr, nc)
    )

这里再次体现：

path 内 → MAX
paths 间 → MIN

Initialization

effort = [
    [float("inf")] * n
    for _ in range(m)
]

effort[0][0] = 0

一开始曾考虑：

float("-inf")

原因是注意到了 path 内部需要不断取 MAX。

但 effort[r][c] 保存的是不同 paths 之间的 minimum，因此未知状态必须为 inf，才能使第一次：

new_effort < effort[r][c]

成立。

Grid state

directions = [
    (-1, 0),
    (0, -1),
    (0, 1),
    (1, 0)
]

neighbor：

nr = r + dr
nc = c + dc

if 0 <= nr < m and 0 <= nc < n:

第一轮实现中曾写成：

0 <= nc < c

这里把当前 column c 与 grid column count n 混淆。合法边界必须由 grid dimensions 决定。

第一轮最核心的问题

1631 暴露的主要问题不是 Grid，而是：

容易把“完整 path 的目标函数”和“到中间 state 为止应该保存什么 information”混在一起。

应该从：

我要找出哪些完整 paths？

转变为：

对于每一个 state，
我需要保存 start → state 的什么 best information？

1976. Number of Ways to Arrive at Destination

基础仍然是标准 shortest path

这题重新回到：

new_dist = current_dist + weight

并且：

if new_dist < dist[neighbor]:

所以 dist 部分与标准 Dijkstra 非常接近。

新问题：同一个 shortest distance 可能有多条 paths

仅仅记录：

dist[node]

无法回答：

达到这个 minimum distance 一共有多少种方式？

因此增加：

ways[node]

定义：

ways[node]
= 从 0 到 node，能够达到 dist[node] 的 shortest path 数量

不需要保存：

parents[node] = [...]

因为最终问题只要求数量，不要求具体 path 来源。

Initialization

dist = [float("inf")] * n
dist[0] = 0

ways = [0] * n
ways[0] = 1

ways[0] = 1 表示一条 empty path，并作为 path counting 的 seed。

两种 relaxation

这是 1976 最重要的新结构。

情况 1：发现更短的路径

if new_dist < dist[neighbor]:
    dist[neighbor] = new_dist

    ways[neighbor] = ways[node]

    heapq.heappush(
        heap,
        (new_dist, neighbor)
    )

旧的 ways[neighbor] 必须丢弃，因为它们对应的旧 distance 已经不再是 shortest distance。

可以记：

< → 替换

情况 2：发现同样短的路径

elif new_dist == dist[neighbor]:
    ways[neighbor] += ways[node]

原来的 shortest paths 仍然有效，而从 current node 过来的 paths 也同样达到 shortest distance，因此累加。

可以记：

== → 累加

例如：

ways[2] = 3
ways[3] = 4

如果通过 2 → 5 和 3 → 5 得到的 distance 都等于 dist[5]：

ways[5] = 3 + 4 = 7

这说明 ways 不是 parent 数量，而是 path 数量。

第一轮实现问题

算法思想已经基本正确，主要实现问题包括：

graph[u] 初始化成 {}，但后面使用 .append()，应初始化成 []；
dist 应为一维 [inf] * n，而不是沿用 1631 的二维结构；
dist, node = heappop(...) 覆盖了整个 dist array，应使用 current_dist；
找到更短路径并更新 dist[neighbor] 后，需要把新的 candidate push 回 heap；
heapq.heappush(heap, item) 的 API 使用错误；
modulo 应使用 % (10**9 + 7)，不是 & (10^9 + 7)。

这些错误大部分属于 representation、variable naming 和 Python API 层面，而不是 Dijkstra 核心逻辑。

787. Cheapest Flights Within K Stops

核心变化：`node` 不足以描述完整 state

最初使用：

prices[node]
stops[node]

这隐含了一个假设：

到达同一个 node 时，只保留 minimum price 的 path 就够了

但 787 中还存在有限资源 flights_used。例如到达同一个 node：

A: price = 100, flights_used = 3
B: price = 150, flights_used = 1

A 更便宜，但消耗了更多 flights；B 更贵，却保留了更多继续向后走的空间。两者存在 trade-off，因此不能仅因为 A 的 price 更低就淘汰 B。

所以：

state ≠ node
state = (node, flights_used)

这题真正把之前的 best[node] 推进到了更一般的 best[state]。

`k stops` 与 `flights_used`

src → A → dst

stops   = 1
flights = 2

因此：

at most k stops
= at most k + 1 flights

起点还没有使用任何 flight：

(src, flights_used = 0)

Best table

定义：

prices[node][flights_used]
= 使用恰好 flights_used 条 flights 到达 node 的 minimum price

合法的 flights_used 为：

0, 1, ..., k + 1

因此第二维需要 k + 2 个位置：

prices = [
    [float("inf")] * (k + 2)
    for _ in range(n)
]
prices[src][0] = 0

k + 2 是状态数量，不表示允许 k + 2 条 flights。

Heap 与 stale check

Heap 必须携带完整 state：

heap = [(0, src, 0)]

即：

(current_price, node, flights_used)

stale check 也针对完整 state：

if current_price > prices[node][flights_used]:
    continue

这里需要继续区分：

current_price
→ 当前 heap state 的 value

prices[node][flights_used]
→ 当前 state 的 authoritative best

new_price
→ 扩展 neighbor 后产生的 candidate

prices[neighbor][new_flights_used]
→ neighbor state 的 authoritative best

Relaxation

new_price = current_price + edge_price
new_flights_used = flights_used + 1

先检查 constraint，再访问二维 table：

if new_flights_used <= k + 1:
    if new_price < prices[neighbor][new_flights_used]:
        prices[neighbor][new_flights_used] = new_price
        heapq.heappush(
            heap,
            (new_price, neighbor, new_flights_used)
        )

不能先访问 prices[neighbor][new_flights_used] 再检查 constraint，否则 new_flights_used = k + 2 时可能越界。

最终答案

到达 dst 可能有多个合法 state：

(dst, 0)
(dst, 1)
...
(dst, k + 1)

题目要求 constraint 内的 minimum price，所以：

minimum_price = min(prices[dst])

return minimum_price if minimum_price != float("inf") else -1

如果手动扫描，minimum_price 应初始化为 inf，不能初始化为 0。

Dominance

对于同一个 node：

B: price = 100, flights = 2
C: price = 120, flights = 3

B 的 price 更低，同时 flights_used 更少，因此 C 被 B dominate，可以淘汰。

但：

A: price = 80,  flights = 4
B: price = 100, flights = 2
D: price = 150, flights = 1

三者都存在 trade-off，不能简单按 minimum price 淘汰其他 states。

第一轮暴露的问题

最初分别维护 prices[node] 和 stops[node]，无法表示 price 与 flights_used 的 trade-off；
stops[src] = 1 不正确，起点应为 flights_used = 0；
new_stop = stops[neighbor] + stops[node] 不正确，flight count 应来自 current path：flights_used + 1；
曾写 new_flights = flights_used += 1，但生成 neighbor state 时不应修改 current state；
stale check 一度把 current_price 与 new_price 混淆；
constraint check 应先于二维 table access；
relaxation 必须更新 prices[neighbor][new_flights_used]，不能覆盖 prices[neighbor] 整行；
final minimum 应从 inf 开始；
minimum_price 已经是 scalar，最终不能再写 minimum_price[dst]。

最核心的迁移

787 的主要问题不是不会写 relaxation，而是最开始把 state 定义得太小。

判断额外信息是否应该进入 state，可以问：

两条 path 到达同一个 node 后，如果这个信息不同，它们未来可做的合法选择是否也会不同？

787 中 flights_used 不同，会改变剩余可使用的 flights，因此它必须进入 state：

state = (node, flights_used)

这也是从普通 Dijkstra 进入 state-space shortest path 的关键一步。

1368. Minimum Cost to Make at Least One Valid Path in a Grid

核心建模：箭头定义 edge weight，而不是 connectivity

最初容易把题目理解成“先顺着箭头一直走，走不通再修改方向”。这是一种以完整 path 为中心的局部 greedy 模拟，但不能保证 global minimum。

更合适的 graph model 是：每个 cell 都可以移动到四个合法相邻 cell；当前箭头指向的方向 edge weight 为 0，其余方向 edge weight 为 1。

state = (r, c)
edge_weight ∈ {0, 1}
cost[r][c] = start → (r,c) 所需的 minimum modification cost
combine = SUM
optimization = MIN

方向编码必须与题目保持一致：

directions = [
    (0, 1),   # 1 right
    (0, -1),  # 2 left
    (1, 0),   # 3 down
    (-1, 0)   # 4 up
]

edge_weight = 0 if i + 1 == grid[r][c] else 1

Dijkstra relaxation

new_cost = current_cost + edge_weight

if new_cost < cost[nr][nc]:
    cost[nr][nc] = new_cost
    heapq.heappush(heap, (new_cost, nr, nc))

本题再次强化了 state-centered view：遍历 edge 的目的不是“把一条 path 走到底”，而是询问“通过 current state 能否改善 neighbor 的 best[state]”。

从 Dijkstra 推导 0-1 BFS

因为所有 edge weights 只有 0 和 1，从一个当前 minimum-cost state 出发，新 candidate 只可能是：

current_cost
current_cost + 1

因此不需要通用 Min Heap，可以用 deque 隐式维护 priority：

if edge_weight == 0:
    dq.appendleft((nr, nc))
else:
    dq.append((nr, nc))

这里不是“优先处理 edge weight 小的 edge”，而是利用 {0,1} 的特殊性质继续保证 total cost 更小的 state 优先传播。

可以统一理解为：

BFS       : edge weight 全为 1       → Queue
0-1 BFS   : edge weight 只有 0 / 1   → Deque
Dijkstra  : arbitrary nonnegative    → Min Heap

`best` table 与 processing structure 的职责

cost[r][c] 才是 authoritative best value；heap / deque 负责决定接下来处理哪些 candidates/states。

0-1 BFS 中 deque 可以只保存 (r,c)，处理时读取：

current_cost = cost[r][c]

同一个 state 可以重复入队。重复处理可能带来额外计算，但不会破坏正确性，因为 relaxation 只接受严格改善：

if new_cost < cost[nr][nc]:

Dijkstra 的 heap 通常还必须保存 candidate cost，因为 Min Heap 需要这个 value 作为 priority key；heapq 不会在排序时动态查询 cost[r][c]。旧 priority 因而可能形成 stale entry，需要 Lazy Deletion。

第一轮暴露的问题

最初把箭头理解成“决定能不能走”，而不是“决定这条 edge 的 cost”；
容易用“顺箭头走到底再修改”的 path simulation 代替 best[state]；
一度混淆 edge_weight、current_cost 和 new_cost；
Dijkstra 实现中曾把初始 candidate push 到临时空 list []，而不是实际的 heap；
理解 0-1 BFS 时，一度把它概括成“优先处理 edge weight 小的”，更准确的是优先维护 total path cost 的顺序。

复杂度

Dijkstra + Heap: O(mn log(mn))
0-1 BFS:         O(V + E) = O(mn)

778. Swim in Rising Water

核心目标：minimize the maximum cell elevation

本题不是把每一步“等待时间”累加。对于一条 path，能够走完整条 path 的最早时间由该 path 上最高的 elevation 决定：

path_time = MAX(cell elevations on path)
answer    = MIN(path_time among all paths)

即：

min over paths (max cell elevation on path)

它与 1631 同属 minimax Dijkstra，但 MAX 的对象不同：

1631: MAX(adjacent height difference)
778 : MAX(cell elevation)

`time[r][c]` 的定义

time[r][c]
= 从 (0,0) 到达 (r,c) 所要求的 minimum water level / minimum time

因此 initialization 必须从语义推导：

time[0][0] = grid[0][0]
heap = [(grid[0][0], 0, 0)]

不能沿用标准 shortest path 的 start = 0，因为起点自身也有 elevation。

Path aggregation

如果：

path = 0 → 5 → 2 → 8

错误思路是：

到 5 等 5
到 2 不等
2 → 8 再等 (8 - 2) = 6
total = 11

问题在于水位是全局时间，不会因为进入 elevation 2 的 cell 就从 5 降回 2。到达 2 时 current_time = 5，进入 8 只需要等到 global time 8。

因此真正比较的是：

current accumulated path requirement
vs
neighbor elevation

而不是 current cell elevation 与 neighbor elevation 的 difference。

正确 relaxation：

new_time = max(current_time, grid[nr][nc])

if new_time < time[nr][nc]:
    time[nr][nc] = new_time
    heapq.heappush(heap, (new_time, nr, nc))

State compression

对于 path：

0 → 5 → 2

未来并不需要保存完整历史。它被压缩为：

current_time = 5

这个 value 已经包含未来计算真正需要的信息：到达当前 state 为止，整条 path 所要求的最高 water level。

这再次说明不能用 current node 自身属性 grid[r][c] 代替到达 state 时已经积累的 path information time[r][c]。

第一轮暴露的问题

最初把题目建模成相邻高度差的累计等待时间，错误使用 SUM；
把 current cell elevation 当成了已经积累的 current_time；
initialization 一度写 time[0][0] = 0；
修改 time[0][0] 后，heap 初始 candidate 一度仍保留 (0,0,0)，导致 best table 与 candidate 语义不一致；
实现中一度把 direction offset dr,dc 当成 neighbor coordinate 使用，写成 grid[dr][dc] / time[dr][dc]，应使用 nr,nc。

与 1631 的统一

1631
state: cell
best: minimum effort
combine: max(current_effort, edge_difference)
paths 间: MIN

778
state: cell
best: minimum required water level
combine: max(current_time, neighbor_elevation)
paths 间: MIN

两题最重要的共同点是：先定义 best[state]，再由它推导 initialization 和 combine，而不是看到 Dijkstra 就默认使用 +。

六、七道题暴露出的共同问题

1. 容易把上一题的 path aggregation 带到下一题

最明显的是从 743 进入 1631 后，多次下意识使用：

current_effort + edge_weight

原因是形成了：

Dijkstra = weights 相加

的印象。

应该固定为：

先问题目如何定义一条 path 的 value，
再决定 combine。

2. 容易混淆 current state 与 neighbor state

Relaxation 的目标始终是：

通过 current
尝试改善 neighbor

所以抽象结构是：

candidate = combine(best[current], edge)

if candidate is better than best[neighbor]:
    best[neighbor] = candidate

1514 中曾出现比较 candidate 与 old_prob、更新 current node 的问题；1631 中曾把 edge_weight 与 effort[neighbor] 混淆。

3. Initialization 容易靠模板而不是语义推导

典型表现：

1514 沿用 start = 0；
1631 因为 path 内取 MAX，考虑把其他 nodes 初始化成 -inf；
1976 一开始考虑 ways[0] = 0。

解决方式不是再背三套初始化，而是每次问：

best[state] 表示什么？
第一次 candidate 应该怎样成功更新它？
start 到自己时，这个 path value 应该是什么？

4. 容易把 heap 当成 best table

Heap 只负责 candidate ordering。

heap ≠ dist
heap ≠ probability
heap ≠ effort

Heap 中可以存在旧 candidate；best table 才是当前 authoritative value。

5. 从完整 path 视角转向 state compression 仍需强化

1631 最明显：

原始视角：
先找到所有 start → end paths，再比较

Dijkstra 视角：
维护 start → 每个 state 的 best information

1976 又进一步：

不保存所有 shortest paths
不保存所有 parents

只保存：
dist[node]
ways[node]

这是一种 state compression：只留下未来计算真正需要的信息。

七、写 Dijkstra 代码前的检查清单

每道题在写代码之前，先回答：

Graph 是 directed 还是 undirected？
Node 编号是 0...n-1 还是 1...n？
state 只是 node，还是 (row, col)，或者还需要更多维度？
edge value 是什么？
best[state] 的精确定义是什么？
一条 path 内，current_value 和 edge_value 如何 combine？
不同 paths 之间，什么叫“better”？
start identity 是什么？
未到达 state 应初始化成什么，才能让第一次 relaxation 成功？
Priority Queue 应该 minimum-first 还是 maximum-first？
heap entry 应该保存哪些足够的信息？
stale entry 的判断方向是什么？
找到 better candidate 后，是否同时更新 best table 并 push heap？
题目是否还要求维护 optimal value 之外的信息，例如 ways？
如果 candidate 与当前 best 相等，需要做什么？
最终返回的是 best value、计数，还是其他状态？

如果这 16 个问题能够在不看模板的情况下回答，代码通常只是这些定义的直接翻译。

八、当前建议记住的统一模板

不要把下面代码当作可直接复制的固定实现，而应把空白部分视为每道题必须重新定义的内容：

best = ...
best[start] = identity

heap = [(priority(start), start)]

while heap:
    current_value, state = heapq.heappop(heap)

    if stale(current_value, best[state]):
        continue

    for neighbor, edge_value in neighbors(state):

        new_value = combine(
            current_value,
            edge_value
        )

        if better(new_value, best[neighbor]):
            best[neighbor] = new_value

            # 如果题目还有额外 state，
            # 在这里同步更新

            heapq.heappush(
                heap,
                (priority(new_value), neighbor)
            )

        elif equal_optimal(new_value, best[neighbor]):
            # 只有类似 1976 的题目才需要
            # 更新额外信息
            ...

真正需要掌握的不是这个 syntax，而是能够为新题自行填写：

identity
priority
stale
combine
better
extra state

九、下一阶段

当前七题已经覆盖：

743   标准 shortest path
1514  MAX objective + PRODUCT path value
1631  minimax path + Grid
1976  shortest path + optimal-path counting
787   constraint-aware state / state-space shortest path
1368  0/1 edge weight + 0-1 BFS
778   minimax path over cell elevation

这一轮已经完成从标准 shortest path 到多个 Dijkstra variants 的迁移。当前最重要的统一认识是：

先定义 state
→ 再定义 best[state]
→ 再确定 path aggregation / combine
→ 再确定 optimization direction
→ 最后选择合适的 processing structure

其中 787 强化了 state design，1368 把 Priority Queue 推进到特殊权重下的 0-1 BFS，778 则再次强化 minimax 与 state compression。

下一阶段不需要继续增加 Dijkstra 模板，而应在后续题目中检查能否独立识别：什么时候是普通 BFS、0-1 BFS、Dijkstra，以及 constraint 是否需要进入 state。

一、题目清单

二、当前掌握情况

三、Dijkstra 的核心原则

1. Dijkstra 的核心不是“把 edge weights 相加”

2. 先定义 best[state] 的语义

3. 区分 path 内部 aggregation 和 paths 之间 optimization

4. Initialization 不是固定模板

5. Priority Queue 与 best table 不能互相替代

6. Stale entry 是 Lazy Deletion 的结果

四、Dijkstra 的不变量与变数

不变骨架

题目决定的变数

五、重点题复盘

743. Network Delay Time

题目建模

Graph representation

第一阶段：不用 Heap

Heap 优化

第一轮暴露的问题

1514. Path with Maximum Probability

最大变化：重新定义“最好”

Initialization

Graph construction

Max Heap

第一轮暴露的问题

核心修正

1631. Path With Minimum Effort

最初思路

Dijkstra 的 state compression

Edge weight

Path aggregation

Relaxation

Initialization

Grid state

第一轮最核心的问题

1976. Number of Ways to Arrive at Destination

基础仍然是标准 shortest path

新问题：同一个 shortest distance 可能有多条 paths

Initialization

两种 relaxation

第一轮实现问题

787. Cheapest Flights Within K Stops

核心变化：node 不足以描述完整 state

k stops 与 flights_used

Best table

Heap 与 stale check

Relaxation

最终答案

Dominance

第一轮暴露的问题

最核心的迁移

1368. Minimum Cost to Make at Least One Valid Path in a Grid

核心建模：箭头定义 edge weight，而不是 connectivity

Dijkstra relaxation

从 Dijkstra 推导 0-1 BFS

best table 与 processing structure 的职责

第一轮暴露的问题

复杂度

778. Swim in Rising Water

核心目标：minimize the maximum cell elevation

time[r][c] 的定义

Path aggregation

State compression

第一轮暴露的问题

与 1631 的统一

六、七道题暴露出的共同问题

1. 容易把上一题的 path aggregation 带到下一题

2. 容易混淆 current state 与 neighbor state

3. Initialization 容易靠模板而不是语义推导

4. 容易把 heap 当成 best table

5. 从完整 path 视角转向 state compression 仍需强化

七、写 Dijkstra 代码前的检查清单

八、当前建议记住的统一模板

九、下一阶段

2. 先定义 `best[state]` 的语义

5. Priority Queue 与 `best` table 不能互相替代

核心变化：`node` 不足以描述完整 state

`k stops` 与 `flights_used`

`best` table 与 processing structure 的职责

`time[r][c]` 的定义