Đại Hội Thuật Toán Cuối Cùng

Buổi 64 — Contest Chặng 7 Dynamic Programming
Points
95
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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
Draft saved