สมมติว่ามี 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 := อาร์เรย์ใหม่ขนาด n เติมด้วย -1
- b_set := แมปใหม่ที่มีคีย์ s - 1
- f := เซตใหม่ที่มีความต่างระหว่างตัวเลข 0 ถึง n และ b_set
- index := 0
- while ขนาดของ b_set > 0:
- สำหรับแต่ละ a ใน b_set: temp_arr[a] := index
- nxt := แมปใหม่ที่มีค่าของ graph ที่ไม่ใช่เซตย่อยของ b_set
- f := ความต่างของ f และ nxt
- b_set := nxt
- index := index + 1
- return ค่าที่ไม่เป็นศูนย์ของ 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
