Python程序:查找两城市之间捷径的距离


假设有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)在edges中,执行:
    • x := x - 1
    • y := y - 1
    • 将y插入graph[x]
    • 将x插入graph[y]
  • temp_arr := 一个包含值为-1的n大小的新数组
  • b_set := 一个包含键s - 1的新映射
  • f := 一个包含0到n的数字与b_set的差集的新集合
  • index := 0
  • 当b_set的大小>0时,执行:
    • 对于b_set中的每个元素a,执行:
      • temp_arr[a] := index
    • nxt := 一个包含graph中不是b_set子集的值的新映射
    • f := f与nxt的差集
    • b_set := nxt
    • index := index + 1
  • 返回temp_arr的非零值

示例

让我们看下面的实现来更好地理解:

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

输入

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

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

3 1 2

更新于:2021年10月6日

412 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告