送货路线：先最少危险站，再最少步数

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练图为有向无权邻接表，起终点计入路径；进入一个危险节点算一次。实际路线双向时显式补反向边。
• 危险数包括起点；若正式约定起点不计，可把初始risk改为0。返回最优二元组，不返回路径。

解题路线

1. 避险版先拒绝危险起终点，再跳过危险邻居。普通BFS足够；示例统一使用堆，以便共用第二问流程。
2. 第二问把边贡献设为(目标节点是否危险,1)，用字典序Dijkstra。每条边贡献非负，弹出的最小二元组标签已定；同危险数下步数更小才更新。
3. 布尔visited在入队时固定节点会丢更好路径。best[u]必须存完整二元组，过期堆项跳过；不能仅记最少步数。非负风险与正步数意味着去掉环总不更差，因此最优可取简单路径。

手动走一遍

s→危险a→t两步，与s→b→c→t三步：第二问选(0,3)，不会因两步更短而选危险路线。若所有路线都至少过一个危险点，则在这些路线中选步数最少的；第一问返回不可达。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from heapq import heappush,heappop

def route(graph,start,target,dangerous,avoid=False):
    # Each arrival at a dangerous node counts once; include the start.
    bad=set(dangerous)
    if avoid and (start in bad or target in bad):return None
    best={start:(int(start in bad),0)};heap=[(*best[start],start)]
    while heap:
        risk,steps,u=heappop(heap)
        if best[u]!=(risk,steps):continue
        if u==target:return risk,steps
        for v in graph.get(u,[]):
            if avoid and v in bad:continue
            score=(risk+int(v in bad),steps+1)
            if v not in best or score<best[v]:
                best[v]=score;heappush(heap,(*score,v))
    return None

复杂度

V节点E边，O((V+E)log(V+E))时间/O(V+E)空间含重复堆项；避险BFS可O(V+E)。

易错点与追问

容易失分的边界

• 用大常数加权危险数但没证明步数上界可能改变目标。
• 不可达返回None与(0,0)区别明确，起终点相同仍按初始risk算。

继续深挖

• 要返回路径时怎样存parent且保持确定平局？
• 若危险为概率而不是计数，为什么应先定义概率聚合公式？