Chương trình tìm số lượng xe buýt tối thiểu cần thiết để đạt được mục tiêu cuối cùng trong python

Giả sử chúng ta có một ma trận n x 3 trong đó mỗi hàng chứa ba trường [src, dest, id] điều này có nghĩa là xe buýt có tuyến đường từ src đến đích. Đi một chiếc xe buýt mới phải mất một đơn vị tiền, nhưng nếu chúng ta ở trên cùng một chuyến xe, chúng ta chỉ phải trả một đơn vị tiền. Chúng tôi phải tìm chi phí tối thiểu cần thiết để đi xe buýt từ địa điểm 0 đến điểm dừng cuối cùng (địa điểm lớn nhất). Nếu không có giải pháp, trả về -1.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 2, vì chúng ta có thể lấy số 0 ở vị trí 0 và ra ở vị trí 3. Sau đó, chúng tôi bắt xe buýt 1 để đến địa điểm 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• start:=0
• target:=vị trí tối đa của ma trận đã cho
• adj:=một bản đồ trống
• đối với mỗi src, dest, id trong các kết nối, thực hiện
  • chèn (đích, id) vào cuối adj [src]
• hp:=a heap với item (0, start, -1)
• đã thấy:=một bản đồ trống
• trong khi hp không trống, hãy thực hiện
  • (cost, cur_pos, cur_bus):=phần tử trên cùng của đống hp và xóa phần trên khỏi hp
  • nếu cur_pos giống với target, thì
    • chi phí trả lại
  • nếu cur_bus in saw [cur_pos], thì
    • chuyển sang lần lặp tiếp theo
  • chèn cur_bus vào [cur_pos] đã thấy
  • đối với mỗi (nex_pos, nex_bus) trong adj [cur_pos], thực hiện
    • next_cost:=cost
    • nếu nex_bus không giống với cur_bus, thì
      • next_cost:=next_cost + 1
    • chèn (next_cost, nex_pos, nex_bus) vào heap hp
• trả về -1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

2