Roads
View as PDF
Submit solution
Points:
0.17 (partial)
Time limit:
2.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
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
Comments
Bài này tính độ phức tạp thế nào nhỉ :o
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.