Roads
Xem dạng PDF
Gửi bài giải
Điểm:
0,17 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Có ~N~ thành phố ~1~ ...~N~ nối bởi các con đường một chiều. Mỗi con đường có hai giá trị: độ dài và chi phí phải trả để đi qua. Bob ở thành phố ~1~. Bạn hãy giúp Bob tìm đường đi ngắn nhất đến thành phố ~N~, biết rằng Bob chỉ có số tiền có hạn là ~K~ mà thôi.
Input
Dòng đầu tiên ghi ~t~ là số test. Với mỗi test:
- Dòng đầu ghi ~K~ (~0 \leq K \leq 10000~).
- Dòng ~2~ ghi ~N~, ~2 \leq N \leq 100~.
- Dòng ~3~ ghi ~R~, ~1 \leq R \leq 10000~ là số đường nối.
- Mỗi dòng trong ~R~ dòng sau ghi ~4~ số nguyên ~S~, ~D~, ~L~, ~T~ mô tả một con đường nối giữa ~S~ và ~D~ với độ dài ~L~ (~1 \leq L \leq 100~) và chi phí ~T~ (~0 \leq T \leq 100~). Lưu ý có thể có nhiều con đường nối giữa hai thành phố.
Output
Với mỗi test, in ra độ dài đường đi ngắn nhất từ ~1~ đến ~N~ mà tổng chi phí không quá ~K~. Nếu không tồn tại, in ra ~-1~.
Sample Input
2
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0
Sample Output
11
-1
Bình luận
Bài này tính độ phức tạp thế nào nhỉ :o
tùy: nếu dijkstra bth thì O((n*n + r) * t)
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.