Hành Trình Miễn Phí K Chặng

Buổi 41 — SPFA & Bellman-Ford
Points
70
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một đồ thị có hướng gồm N đỉnh và M cạnh có trọng số (có thể âm, đảm bảo không có chu trình âm). Bạn có K vé đặc biệt; mỗi vé cho phép bạn biến trọng số của một cạnh bất kỳ trên đường đi thành 0 (bạn có thể chọn dùng ít hơn K vé hoặc không dùng vé nào). Hãy tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh N.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên N và M.
  • M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w.
  • Dòng cuối cùng chứa số nguyên K.
Dữ liệu ra
  • Một số nguyên duy nhất là chi phí nhỏ nhất để đi từ 1 đến N, hoặc IMPOSSIBLE nếu không có đường đi.
Ví dụ
Input Output
4 5
1 2 10
2 3 -5
3 4 8
1 3 100
2 4 20
1
3
3 1
1 2 -10
2
IMPOSSIBLE
Giới hạn
  • 1 ≤ N ≤ 1000
  • 0 ≤ M ≤ 3000
  • 0 ≤ K ≤ 10
  • 1 ≤ u, v ≤ N
  • -10^6 ≤ w ≤ 10^6
Draft saved