用 Python 编写程序，找出两座城市之间的捷径长度

pythonserver side programmingprogramming更新于 2025/12/2 19:24:17

假设有 n 个城市，这些城市通过两种道路相连:高速公路和捷径。现在，有一张地图，地图上只有高速公路，没有捷径。城市的交通部门希望推出一种利用高速公路和捷径连接城市的交通方式。我们知道，如果两座城市之间没有高速公路，那么就有捷径。我们的任务是找到从起始城市到所有其他城市的最短距离捷径。

因此，如果输入如下

起始顶点 (s) 为 1，则输出为 3 1 2。

如果我们只走捷径，城市 1 和 2 之间的路径为 1->3->4->2，成本为 3。

类似地，

1 和 3:1->3，成本为 1。

1 和 4: 1->3->4，成本 2。

为了解决这个问题，我们将遵循以下步骤 −

graph := 一个包含 n 个集合的新列表
对于边中的每一对 (x, y)，执行
- x := x - 1
- y := y - 1
- 将 y 插入 graph[x]
- 将 x 插入 graph[y]
temp_arr := 一个大小为 n 的新数组，包含值 -1
b_set := 一个包含键 s - 1 的新映射
f := 一个包含数字 0 到 n 和 b_set 之间的集合差的新集合
index := 0
当 b_set 的大小 > 0 时，执行
- 对于 b_set 中的每个元素 a，执行
  - temp_arr[a] := index
- nxt := 一个新的映射，其中包含不是 b_set 子集的图的值
- f := f 和 nxt 的集合差
- b_set := nxt
- index := index + 1
返回 temp_arr 的非零值

示例

让我们看看下面的实现以便更好地理解 −

def solve(n, edges, s):
    graph = [set() for i in range(n)]
    for (x, y) in edges:
        x -= 1
        y -= 1
        graph[x].add(y)
        graph[y].add(x)
    temp_arr = [-1] * n
    b_set = {s - 1}
    f = set(range(n)).difference(b_set)
    index = 0
    while len(b_set) > 0:
        for a in b_set:
            temp_arr[a] = index
        nxt = {f for f in f if not b_set.issubset(graph[f])}
        f = f.difference(nxt)
        b_set = nxt
        index += 1
    return (' '.join(str(t) for t in temp_arr if t > 0))    

print(solve(4, [(1, 2), (2, 3), (1, 4)], 1))