Nhà Thanh ở thành phố A,
nhà Lê ở thành phố B, cuối tuần Thanh và Lê được nghỉ nên Thanh quyết định đến
thành phố B để thăm Lê. Tuy nhiên Thanh chỉ có K đồng nên rất có thể
Thanh phải đi xe buýt đến 1 số thành phố khác rồi mới tiếp tục đến B.
Việc di chuyển qua nhiều thành phố có thể mất nhiều thời gian do vậy bạn hãy
giúp Thanh tìm ra một hành trình đi từ A đến B sao cho thời gian di
chuyển là ít nhất và Thanh vẫn còn tiền khi đến B. Biết rằng:
Có N thành phố được đánh số từ 1 đến N
(bao gồm cả A và B), giữa hai thành phố u
và v
có thể thể có tuyến xe buýt hoặc không, nếu có thì bạn được biết từ thành phố u
đến v
đi bằng xe buýt sẽ mất t thời gian và tốn x
đồng.
Dữ liệu vào: Từ tệp
văn bản THANHLEE.INP
+ Dòng đầu tiên ghi 3 số nguyên K,
N,
M
cho biết K là số đồng mà Thanh có, N là số lượng thành phố, M
là số lượng các cặp thành phố có tuyến xe buýt.
+ M dòng tiếp theo mỗi dòng ghi 4 số
nguyên u, v, t, x cho biết thông tin về tuyến xe buýt giữa thành phố u
và v
mất t
thời gian và x đồng.
+ Dòng cuối cùng ghi hai số nguyên A
và B
Các số trên cùng 1 dòng cách nhau ít nhất
1 ký tự trắng.
Dữ liệu ra: Một số
nguyên thỏa yêu cầu của bài toán, nếu không có cách đi thì in ra số -1.
Giới hạn:
+ Trong tất cả các test: 1 ≤ K
≤ 200; 2 ≤ N ≤ 2 000; 1 ≤ M ≤ 10 000; 1≤ t ≤ 105; 0≤ x
≤200
+ Có 20% số điểm tương ứng với K=1
và N≤200
+ Có 20% số điểm tương ứng với K=1
và 200<N≤2000
Ví dụ:
|
THANHLEE.INP
|
THANHLEE.OUT
|
|
THANHLEE.INP
|
THANHLEE.OUT
|
|
10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4
|
7
|
|
3 3 3
1 2 5 1
3 2 8 2
1 3 1 3
1 3
|
-1
|
|
Đường đi: 1→2 →3→4
|
|
Không thể đi từ 1 qua 3
|
||
