🎯 Mục tiêu bài học

  • Đọc đề và nhận ra "bài này là loại gì?".
  • Kết hợp nhiều mảng kiến thức trong 1 bài (thường là bài Bài 3/Bài 4 trong đề thi).
  • Quản lý trạng thái, ràng buộc, và điều kiện tối ưu.

📘 1️⃣ Kiểu bài thi rất hay ra

Ví dụ: "Cho đồ thị có n đỉnh, m cạnh, mỗi cạnh có trọng số w. Em phải đi từ 1 đến n sao cho tổng chi phí nhỏ nhất, nhưng không được dùng quá K cạnh đắt (w > L)."

Đây không còn chỉ là Dijkstra nữa. Vì ngoài khoảng cách, ta còn theo dõi số cạnh đắt đã dùng. Đó chính là DP trên đồ thị (stateful shortest path).

📗 2️⃣ Ý tưởng lời giải

  • Trạng thái: dist[node][bad] = chi phí tối thiểu để đến đỉnh node khi đã dùng bad cạnh đắt.
  • Dùng hàng đợi ưu tiên (Dijkstra trên trạng thái mở rộng).

🌿 Python mô phỏng ý tưởng

import heapq
INF = 10**18
n,m,K,L = map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
    u,v,w=map(int,input().split())
    g[u].append((v,w))
    g[v].append((u,w))

dist=[[INF]*(K+1) for _ in range(n+1)]
dist[1][0]=0
pq=[(0,1,0)]  # (cost,node,bad_used)

while pq:
    cost,u,bad = heapq.heappop(pq)
    if cost!=dist[u][bad]: continue
    for v,w in g[u]:
        nb = bad + (1 if w>L else 0)
        if nb<=K:
            nc = cost + w
            if nc < dist[v][nb]:
                dist[v][nb]=nc
                heapq.heappush(pq,(nc,v,nb))

ans = min(dist[n])
print(ans if ans

Điểm quan trọng: đây là Graph + DP trạng thái + ràng buộc toán (số cạnh đắt ≤ K).

📘 3️⃣ Bài luyện tương tự

  1. Đi qua tất cả điểm bắt buộc (subset DP trên đồ thị nhỏ).
  2. Đếm số đường đi thỏa điều kiện chia hết (graph + modular DP).
  3. Tối đa hóa điểm thưởng thay vì tối thiểu hóa chi phí (đảo chiều tư duy).

🧩 Bài tập thi thử

  1. Viết lại lời giải trên bằng C++ với priority_queue.
  2. Nếu K = 0 thì thuật toán rút gọn thành gì?
  3. Nếu L = 0 (mọi cạnh đều "đắt"), đề trở thành bài toán kinh điển nào?
💡 Gợi ý câu 2 
K = 0 nghĩa là không được đi qua cạnh đắt.
→ Chỉ chạy Dijkstra trên các cạnh w ≤ L.
⬅️ Quay lại chương 14