在 Python 中找出两个城市之间的快捷方式长度的程序

Z时代
2024-01-10
分类：综合

假设有 n 个城市，并且城市与两种类型的道路相连；高速公路和捷径。现在，有一张映射，映射上只有高速公路，所有的捷径都没有。城市交通部门希望推出一种利用高速公路和捷径连接城市的交通方式。当两个城市之间没有高速公路时，我们知道它们之间有一条捷径。我们的任务是找到从起始城市到所有其他城市的捷径的最小距离。

所以，如果输入像

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

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

相似地，

1 和 3：1->3，成本 1。

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

示例

让我们看看以下实现以更好地理解 -

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))