|
|
Từ tập các bài có trên SPOJ (acm)
338. Roads
Mã bài: ROADS
|
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.
Dữ liệu
Dòng ðầu tiên ghi t là số test. Với mỗi test, dòng ðầu ghi K (0 ≤ K ≤ 10000). Dòng 2 ghi N, 2 ≤ N ≤ 100. Dòng 3 ghi R, 1 ≤ R ≤ 10000 là số ðường nối. Mỗi dòng trong N 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 ≤ L ≤ 100) và chi phí T (0 ≤ T ≤ 100). Lưu ý có thể có nhiều con ðường nối giữa hai thành phố.
Kết quả
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.
Ví dụ
Dữ liệu
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
Kết quả
11
-1
| Được gửi lên bởi: | Ngô Minh Ðức |
| Ngày: | 2005-04-28 |
| Thời gian chạy: | 7s
|
| Giới hạn mã nguồn: | 50000B |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: AWK CLOJ ERL F# GO JS PERL 6 PYTH 3.1.2 SCALA SED TCL |
| Nguồn bài: | Central European Olympiad in Informatics '98 |
|
|
|
|
