【面经】Stripe Coding：自行车路线规划 —— K 条最便宜的简单路径（过滤+复合成本）

分享一道我 Stripe 电面遇到的题：城市地图上的自行车路线规划。说实话这一轮难的不是题，是和面试官的沟通，就这样吧。把题和我的解法贴出来供讨论。

**题面。** 地图是一个无向带权图，每条路是 `(u, v, distance, bike_lane, elevation_gain, traffic_risk)`，一条路的骑行成本是 `distance + 2 * elevation_gain + 3 * traffic_risk`。给定 `start`、`end`、`k`、`require_bike_lanes` 开关和一份 `closed_roads`（无向对，`(u, v)` 和 `(v, u)` 是同一条路），返回 k 条最便宜的**简单路径**（不重复经过同一个路口），形式是 `(total_cost, path)`，按总成本升序、成本相同按路径字典序排序。不足 k 条就全返回。`start == end` 时直接返回 `[(0, [start])]`，哪怕一条路都没有。无路可走返回 `[]`。

两个例子。（1）8 条路的图，k=3，不做过滤 → `[(9, [0,3,4]), (12, [0,1,4]), (12, [0,2,4])]`，注意两条成本 12 的路线按字典序排。（2）`require_bike_lanes=True` 且 0-3 这条路关闭（在关闭列表里写的是 `(3, 0)`）时，只剩 `[(4, [0,2,3])]`：0-1 没有自行车道被过滤，0-3 直达路被关了（哪怕列表里写的是反方向）。

**第一步是过滤建图。** 每次调用都在函数内重新建图——`closed_roads` 每次调用都可能不同（这就是题里说的动态更新），不能跨调用缓存。关闭对按两个方向都放进集合；然后删掉关闭的路，按开关删掉没有自行车道的路，边权就是复合成本：

```python
def build_graph(roads, require_bike_lanes, closed_roads):
    closed = set()
    for u, v in closed_roads:
        closed.add((u, v))
        closed.add((v, u))                      # 关闭对是无向的
    adj = {}
    for (u, v, distance, bike_lane, elev, risk) in roads:
        if (u, v) in closed:
            continue
        if require_bike_lanes and bike_lane != 1:
            continue
        w = distance + 2 * elev + 3 * risk
        adj.setdefault(u, []).append((v, w))
        adj.setdefault(v, []).append((u, w))
    return adj
```

**方法 A —— 对部分路径做 best-first 枚举。** 优先队列里放部分路径，键是 `(cost, path)`。每次弹出最便宜的部分路径：如果它正好到 `end`，就是下一条答案；否则向每个不在当前路径上的邻居延长一步。因为每条路成本为正，完整路径从队列里弹出的顺序恰好就是题目要求的顺序——而且键里带了路径本身，成本相同时自动按字典序弹出，排序规则不需要任何额外处理。

```python
import heapq

def solution(roads, start, end, k, require_bike_lanes, closed_roads):
    if start == end:
        return [(0, [start])]
    adj = build_graph(roads, require_bike_lanes, closed_roads)
    results, heap = [], [(0, [start])]
    while heap and len(results) < k:
        cost, path = heapq.heappop(heap)
        if path[-1] == end:
            results.append((cost, path))
            continue
        on_path = set(path)
        for nxt, w in adj.get(path[-1], []):
            if nxt not in on_path:
                heapq.heappush(heap, (cost + w, path + [nxt]))
    return results
```

代价：第 k 条路线弹出时搜索就停，但在此之前展开的部分路径数量最坏是指数级的（稠密图）。这道题的规模（n ≤ 100，k ≤ 10）实际跑没问题；最坏情况靠方法 B 兜底。

**方法 B —— Yen 算法。** 先用 Dijkstra 求最短路线；然后反复取最后一条已接受的路线，在它每个 spur 位置上：禁掉已接受路线从同一 root 前缀出发的那条边，禁掉 root 里的其他节点，从 spur 节点向 `end` 再跑一次 Dijkstra，每次得到一条候选，取最便宜的候选作为下一条路线。两个细节是关键：

- Dijkstra 本身要返回「最便宜里字典序最小」的那条——堆的键用 `(cost, path)` 就自然成立；
- **边界平局：** 恰好收满 k 条就停，可能丢掉一条与第 k 条成本相同、但字典序更小的路线。所以要继续接受，直到下一候选的成本大于第 k 条的成本，最后统一按 `(cost, path)` 排序再截断到 k。

每条路线的复杂度是多项式的：O(n) 个 spur 位置 × 每个位置一次 Dijkstra。

**我记下的坑：**
- 把关闭对当成有向的——`(3, 0)` 必须能关掉 0-3；
- 只按成本排序、把平局丢给运气：平局规则必须在搜索内部就成立（方法 A 靠堆的键），最后才排序是救不回来已被搜索截断掉的路线的；
- 跨调用缓存过滤后的图——`closed_roads` 作为入参就是因为它会变；
- `start == end` 要在过滤之前短路处理：没有路时也要返回 `[(0, [start])]`。

*验证说明：* 发帖前实现实际跑过：两个给定例子、上面全部边界情况、在 3,000 个随机小图上和暴力枚举全部简单路径对比、再在 300 个中型图上交叉验证方法 A 与方法 B——结果全部一致。

觉得有帮助的话欢迎收藏、加米，谢谢。