資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究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
- 對於b_set中的每個元素a，執行：
- 返回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))
輸入
4, [(1, 2), (2, 3), (1, 4)], 1
輸出
3 1 2
更新於：2021年10月6日
412 次瀏覽
廣告