Hành Trình Miễn Phí K Chặng
Points
70
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề 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
IMPOSSIBLEnế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
Community Discussion