資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：找出公民能夠到達市場的最小成本
假設有n個城市和m條連線這些城市的道路。市民需要市場來購買商品。現在，城市裡沒有市場，城市之間的道路正在建設中。如果滿足以下條件，則可以在兩個城市之間修建雙向道路：(i) 該城市包含一個市場；(ii) 可以透過連線有市場的道路到達這些城市。修建道路的成本為x，修建市場的成本為y，兩者均已給出。我們需要找出使每個城市的市民都能到達市場的最小成本。陣列'cities'包含有關城市的資訊，說明哪些城市可以透過道路連線。
因此，如果輸入類似於n = 4，m = 3，x = 1，y = 2，cities = [[1, 2], [2, 3], [3, 4]]，則輸出將為4。
在這裡，我們可以看到四個城市1、2、3和4。如果在城市1處建立一個市場，並在(1, 4)和(1,3)之間修建兩條道路，則總成本將為2 + 1 + 1 = 4。這是最小成本。
為了解決這個問題，我們將遵循以下步驟：
- 如果x <= y，則
- 返回n * x
- 否則，
- adj_list := 一個包含列表作為元素的對映
- 對於cities中的每個城市，執行以下操作：
- city1 := city[0]
- city2 := city[1]
- 將city2插入adj_list[city1]的末尾
- 將city1插入adj_list[city2]的末尾
- temp := 一個大小為(n + 1)的新列表，初始化值為True
- value := 0
- dq := 一個雙端佇列
- 對於cur從1到n + 1，執行以下操作：
- 如果temp[cur]不為零，則
- value := value + x
- 將cur插入dq的最右邊
- temp[cur] := False
- 當dq不為空時，執行以下操作：
- 對於dq中提取的左側元素的每個相鄰元素i，執行以下操作：
- 如果temp[i]不為零，則
- 將i插入dq的最右邊
- temp[i] := False
- value := value + y
- 如果temp[i]不為零，則
- 如果temp[cur]不為零，則
- 返回value
示例
讓我們看看以下實現以更好地理解：
from collections import defaultdict, deque
def solve(n, m, x, y, cities):
if x <= y:
return n * x
else:
adj_list = defaultdict(list)
for city in cities:
city1 = city[0]
city2 = city[1]
adj_list[city1].append(city2)
adj_list[city2].append(city1)
temp = [True] * (n + 1)
value = 0
dq = deque()
for cur in range(1, n + 1):
if temp[cur]:
value += x
dq.append(cur)
temp[cur] = False
while dq:
for i in adj_list[dq.popleft()]:
if temp[i]:
dq.append(i)
temp[i] = False
value += y
return value
print(solve(4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]))輸入
4, 3, 2, 1, [[1, 2], [2, 3], [3, 4]]
輸出
4
更新於： 2021年10月23日
264 次檢視
廣告