最近喜爱城市：同一最短层全部返回

题意与假设

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

• 训练图无权有向，城市ID唯一，路线双向则补双向边。输出BFS发现顺序；不保证字典序。
• 起点自身若在favorite中，零距离仅返回起点；不可达全返回空。权重和交通约束未给。

解题路线

1. BFS记录最短distance，发现第一个favorite时确定最佳层d。继续处理队列里距离d的节点，收集所有favorite，遇下一层即可停止。
2. 无需从每个favorite各跑一次；一个source的层序已同时得到全部候选距离。全局visited首次发现标记，防重复路线入队及重复输出。
3. 一旦知道最佳层，不需再扩展其节点。此前同层非favorite可能已入队更深节点，但它们会被停止条件挡住。权重版要Dijkstra并处理所有等最优距离节点，零权边可能连接更多同层喜爱节点。

手动走一遍

s连a和b，两者都favorite：返回a/b，不能在a处立即return。s本身favorite，则距离0比任何可达别城更近。

Python 参考实现

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

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

from collections import deque

def nearest(graph,start,favorites):
    wanted=set(favorites);queue=deque([start]);distance={start:0};found=[];best=None
    while queue:
        u=queue.popleft();d=distance[u]
        if best is not None and d>best:break
        if u in wanted:found.append(u);best=d
        if best is None:
            for v in graph.get(u,[]):
                if v not in distance:distance[v]=d+1;queue.append(v)
    return found

复杂度

O(V+E)最坏时间/O(V)空间，输出F另Ω(F)；若要排序结果需O(FlogF)。

易错点与追问

容易失分的边界

• 只保留单个closest会漏并列。
• 用DFS第一次遇到喜爱城市不保证最短。

继续深挖

• 有零权边时Dijkstra同距离停止规则如何调整？
• 大量不同起点查询时多源反向BFS如何返回全部并列favorite？