หา Cost ต่ำสุดไปถึงจุดสิ้นสุดด้วย Bus Routes (Dijkstra + State) ใน Python

ปัญหา: กำหนด Bus Routes `[[src, dest, bus_id], ...]` เริ่มที่ Location 0 ไป Location สูงสุด (Max Location) Cost = จำนวน Bus ที่ขึ้น (ขึ้น Bus เดียวต่อเนื่อง = 1 Cost, เปลี่ยน Bus = +1 Cost)

Model: **Shortest Path on State Graph** State = `(location, current_bus)` Edge = Ride Bus หรือ Switch Bus

อัลกอริทึม: Dijkstra on (Location, Bus) State

1. Build Adjacency: `adj[src] = [(dest, bus_id), ...]`
2. Priority Queue: `(cost, location, current_bus)` เริ่ม `(0, 0, -1)`
3. Visited Set: `seen[location] = set(bus_ids)` ป้องกันซ้ำ State
4. Pop Min Cost → ถ้า Location = Target → Return Cost
5. Expand: ขึ้น Bus ถัดไปจาก `adj[location]` คำนวณ `next_cost = cost + (bus != current_bus)`

การติดตั้ง

from collections import defaultdict
from heapq import heappush, heappop

class Solution:
    def solve(self, connections):
        start = 0
        target = max(max(u, v) for u, v, _ in connections)
        
        # Build Graph
        adj = defaultdict(list)
        for src, dest, bus_id in connections:
            adj[src].append((dest, bus_id))
        
        # Dijkstra
        pq = [(0, start, -1)]  # (cost, location, current_bus)
        seen = defaultdict(set)
        
        while pq:
            cost, loc, bus = heappop(pq)
            
            if loc == target:
                return cost
            
            if bus in seen[loc]:
                continue
            seen[loc].add(bus)
            
            for nxt_loc, nxt_bus in adj[loc]:
                next_cost = cost + (1 if nxt_bus != bus else 0)
                heappush(pq, (next_cost, nxt_loc, nxt_bus))
        
        return -1  # Unreachable

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

คำอธิบาย

• Target = Max Location ใน Connections (ตัวอย่าง = 5)

• State = `(location, bus_id)` Bus=-1 = ยังไม่ขึ้น Bus ไหน

• Cost เพิ่มเมื่อ `next_bus != current_bus` (Switch Bus)

• Dijkstra ให้ Minimum Cost เพราะ Edge Weight = 0 หรือ 1 (Non-negative)

Trace ตัวอย่าง

Start: (0, 0, -1) Cost=0
→ Take Bus 0 to 1: Cost=1 (Switch from -1)
→ Take Bus 0 to 2: Cost=1 (Same Bus)
→ Take Bus 0 to 3: Cost=1 (Same Bus)
→ Take Bus 1 to 5: Cost=2 (Switch to Bus 1)
→ Reach Target 5 with Cost=2 ✓

Alternative: Bus 0 to 3 → Bus 2 from 5? No, Bus 2 is 5→0 (Wrong direction)

Complexity

• States: O(V × B) โดย V = Locations, B = Unique Buses
• Time: O(E log V) โดย E = Transitions
• Space: O(V × B)

Variations

# 0-1 BFS (เร็วกว่า Dijkstra สำหรับ Weight 0/1)
from collections import deque
dq = deque([(0, start, -1)])
while dq:
    cost, loc, bus = dq.popleft()
    ...
    if nxt_bus == bus:
        dq.appendleft((cost, nxt_loc, nxt_bus))  # Weight 0
    else:
        dq.append((cost+1, nxt_loc, nxt_bus))    # Weight 1

# Multi-source / Multi-target
# Time-dependent Schedules
# Transfer Penalties