Đại Hội Thuật Toán Cuối Cùng
Points
95
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị có hướng có trọng số gồm N đỉnh và M cạnh. Có Q truy vấn, mỗi truy vấn cho (u, v, k): tìm đường đi ngắn nhất từ u đến v sao cho đường đi đi qua tối đa k cạnh. Nếu không có đường đi, in -1.
Sử dụng thuật toán Bellman-Ford biến thể (hoặc DP trên số cạnh) để giải.
Dữ liệu vào
Dòng 1: Ba số nguyên N, M, Q (1 ≤ N ≤ 200, 1 ≤ M ≤ N*(N-1), 1 ≤ Q ≤ 10^4) M dòng tiếp theo: u, v, w (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w ≤ 10^6) Q dòng tiếp theo: u, v, k (1 ≤ u, v ≤ N, 1 ≤ k ≤ N)
Dữ liệu ra
Q dòng, mỗi dòng một số nguyên — đường đi ngắn nhất hoặc -1.
Ví dụ
| Input | Output |
|---|---|
| 4 5 3\n1 2 10\n2 3 20\n1 3 50\n3 4 5\n1 4 100\n1 4 2\n1 4 3\n1 3 1 | 55\n35\n50 |
Giới hạn
- 1 ≤ N ≤ 200
- 1 ≤ M ≤ N*(N-1)
- 1 ≤ Q ≤ 10^4
- 1 ≤ w ≤ 10^6
- Không có cạnh âm
Community Discussion