Amazon VO：免费公交加步行，怎样判断 K 街以内可达？

题意与假设

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

• 街道为无障碍二维整数网格，可在站点/start/end之间自由步行；k约束累计步行，不是每段单独上限。
• 公交乘坐不耗步行预算，没有换乘/时间限制，公交只沿给定双向边。
• 道路阻挡、单向路、票价与时刻表未公开，不补入原题。

解题路线

1. 顶点为所有站点加start/end，公交连接边权0；任意两点可以步行，边权为Manhattan distance。这是非负权最短路，目标最短步行≤k。
2. 为何离散站点足够：每段公交前后都在站点切换，纯步行无障碍时由三角不等式可压成两端曼哈顿最短路径；中间非站点不会产生更低步行成本。
3. Dijkstra从start开始松弛所有顶点，免费公交边取0。一个公交连通分量里的站点可零成本互达，可先DSU缩分量，但分量间步行距离要取成员点最近距离，不能只拿代表点坐标。
4. 不要只连接距离≤k的步行边然后普通BFS判连通，因为多次短步行总和可能>k；必须累计边权。也不能用0-1 BFS，步行权不只0/1。
5. 当前dense隐式图便于正确性与对照，很多站点时O(S²)不可直接扩；几何稀疏化需要单独证明候选边保最短路，不凭“每站只留几个最近站”宣称精确。

手动走一遍

训练start=(0,0),end=(100,0)，公交(2,0)↔(98,0)，最小步行2+2=4，因此k=3不可达、k=4可达。直走需要100。

Python 参考实现

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

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

from heapq import heappop,heappush


def minimum_walking(start,end,bus_edges):
    """Any pair can be walked by Manhattan distance; bus edges undirected, walking cost 0."""
    nodes=sorted({start,end}|{point for edge in bus_edges for point in edge})
    index={point:i for i,point in enumerate(nodes)}
    free={frozenset(edge) for edge in bus_edges}
    distance=[float('inf')]*len(nodes)
    origin=index[start]
    destination=index[end]
    distance[origin]=0
    heap=[(0,origin)]
    while heap:
        cost,at=heappop(heap)
        if cost!=distance[at]:continue
        if at==destination:return cost
        a=nodes[at]
        for nxt,b in enumerate(nodes):
            weight=0 if frozenset((a,b)) in free else abs(a[0]-b[0])+abs(a[1]-b[1])
            candidate=cost+weight
            if candidate<distance[nxt]:
                distance[nxt]=candidate
                heappush(heap,(candidate,nxt))
    raise AssertionError("walking provides connectivity")

复杂度

S不同点，示例dense松弛O(S² log S)保守时间界，堆最多O(S²)记录、distance O(S)，输入公交边O(E)；稠密无堆Dijkstra可O(S²)时间与O(S+E)状态。

易错点与追问

容易失分的边界

• 每段≤k就判断整体≤k。
• 普通BFS不累加步行长度。
• DSU代表坐标代替分量最近距离。
• 免费公交理解为所有站点彼此免费。

继续深挖

• 限制换乘次数需要什么状态？
• 公交时间也要优化时如何多目标？
• 街道有障碍时如何计算步行边？