โปรแกรมค้นหาจำนวนบัสขั้นต่ำที่ต้องใช้เพื่อไปให้ถึงเป้าหมายสุดท้ายใน python

สมมติว่าเรามีเมทริกซ์ขนาด n x 3 ซึ่งแต่ละแถวมีสามฟิลด์ [src, dest, id] ซึ่งหมายความว่าบัสมีเส้นทางจาก src ไปยังปลายทาง ขึ้นรถเมล์คันใหม่ต้องใช้เงินหน่วยเดียว แต่ถ้าขึ้นรถบัสคันเดิมต้องจ่ายแค่หน่วยเดียว เราต้องหาต้นทุนขั้นต่ำที่จำเป็นในการขึ้นรถบัสจากตำแหน่ง 0 ไปยังป้ายสุดท้าย (ตำแหน่งที่ใหญ่ที่สุด) หากไม่มีวิธีแก้ปัญหา ให้คืนค่า -1

ดังนั้นหากอินพุตเป็นแบบ

แล้วเอาท์พุตจะเป็น 2 เนื่องจากเราสามารถเอา 0 ที่ตำแหน่ง 0 และออกที่ตำแหน่ง 3 จากนั้นเราขึ้นรถบัส 1 ไปยังตำแหน่งที่ 5

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เริ่ม :=0
• เป้าหมาย :=ตำแหน่งสูงสุดของเมทริกซ์ที่กำหนด
• adj :=แผนที่ว่างเปล่า
• สำหรับแต่ละ src, dest, id ในการเชื่อมต่อ ทำ
  • แทรก (dest, id) ที่ส่วนท้ายของ adj[src]
• hp :=ฮีปที่มีไอเท็ม (0, start, -1)
• เห็น :=แผนที่ว่างเปล่า
• ในขณะที่แรงม้าไม่ว่างให้ทำ
  • (ราคา, cur_pos, cur_bus) :=องค์ประกอบด้านบนของฮีป hp และลบด้านบนออกจาก hp
  • ถ้า cur_pos เหมือนกับเป้าหมาย
    • ค่าส่งคืน
  • ถ้าเห็น cur_bus ใน[cur_pos] แล้ว
    • ติดตามตอนต่อไป
  • แทรก cur_bus ลงใน seen[cur_pos]
  • สำหรับแต่ละ (nex_pos, nex_bus) ใน adj[cur_pos] ทำ
    • next_cost :=ราคา
    • ถ้า nex_bus ไม่เหมือนกับ cur_bus แล้ว
      • next_cost :=next_cost + 1
    • แทรก (next_cost, nex_pos, nex_bus) ลงในฮีป hp
• คืน -1

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

from collections import defaultdict
from heapq import heapify, heappop, heappush
class Solution:
   def solve(self, connections):
      start = 0
      target = max(max(y, x) for y, x, _ in connections)

      adj = defaultdict(list)
      for f, t, id in connections:
         adj[f].append((t, id))

      hp = [(0, start, -1)]
      seen = defaultdict(set)

      while hp:
         cost, cur_pos, cur_bus = heappop(hp)
         if cur_pos == target:
            return cost
         if cur_bus in seen[cur_pos]:
            continue
         seen[cur_pos].add(cur_bus)

         for nex_pos, nex_bus in adj[cur_pos]:
            next_cost = cost
            if nex_bus != cur_bus:
               next_cost += 1
            heappush(hp, (next_cost, nex_pos, nex_bus))

      return -1

ob = Solution()
matrix = [
   [0, 1, 0],
   [1, 2, 0],
   [2, 3, 0],
   [3, 5, 1],
   [5, 0, 2]
]
print(ob.solve(matrix))

อินพุต

matrix = [[0, 1, 0],  
[1, 2, 0],  
[2, 3, 0],  
[3, 5, 1],  
[5, 0, 2]]

ผลลัพธ์

2