Lộ trình K xe tải
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cần điều phối $K$ xe tải đi từ trạm xuất phát $1$ đến trạm đích $N$ trên đồ thị có hướng gồm $N$ đỉnh và $M$ cung. Mỗi cung $(u, v)$ có chi phí đi qua là $w$.
Để tránh ùn tắc, không có hai xe tải nào được đi qua cùng một trạm trung gian (tức là các lộ trình phải phân biệt về đỉnh, ngoại trừ đỉnh $1$ và đỉnh $N$), và mỗi cung chỉ được đi qua tối đa bởi 1 xe.
Hãy tìm tổng chi phí nhỏ nhất cho $K$ xe tải, hoặc in ra -1 nếu không thể sắp xếp đủ $K$ lộ trình.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, K$ ($2 \le N \le 200, 1 \le M \le 2000, 1 \le K \le 20$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N, 0 \le w \le 10^5$).
Dữ liệu ra
- In ra tổng chi phí nhỏ nhất, hoặc
-1nếu không thể.
Ví dụ
| Input | Output |
|---|---|
| 5 6 2 1 2 2 2 5 3 1 3 1 3 4 2 4 5 1 2 4 1 |
9 |
Giới hạn
- $2 \le N \le 200, 1 \le M \le 2000, 1 \le K \le 20$.
- Thời gian chạy: 2 giây.
Community Discussion