Đường Đi Tối Đa K Cạnh
Points
35
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 và có thể tồn tại chu trình âm). Hãy tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh N sử dụng tối đa K cạnh.
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
- In ra tổng trọng số nhỏ nhất của đường đi từ 1 đến N dùng tối đa K cạnh, hoặc
IMPOSSIBLEnếu không có đường đi thỏa mãn.
Ví dụ
| Input | Output |
|---|---|
| 4 4 1 2 1 2 3 -5 3 2 1 3 4 2 3 |
-2 |
| 4 3 1 2 1 2 3 1 3 4 1 2 |
IMPOSSIBLE |
Giới hạn
- 1 ≤ N ≤ 1000
- 0 ≤ M ≤ 5000
- 1 ≤ K ≤ N
- -10^6 ≤ w ≤ 10^6
Community Discussion