Ông G là một hướng dẫn viên du lịch.
Công việc của ông ta là hướng dẫn một vài “tua” du lịch từ thành phố này đến
thành phố khác. Trên các thành phố này, có một vài con đường hai chiều được nối
giữa chúng. Mỗi cặp thành phố có đường kết nối đều có dịch vụ xe buýt chỉ chạy
giữa hai thành phố này và chạy theo đường nối trực tiếp giữa chúng. Mỗi dịch vụ
xe buýt đều có một giới hạn lớn nhất lượng khách mà xe buýt có thể trở được.
Ông G có một tấm bản đồ chỉ các thành phố và những con đường nối giữa chúng.
Ngoài ra, ông ta cũng có thông tin về mỗi dịch vụ xe buýt giữa các thành phố.
Ông hiểu rằng ông không thể đưa tất cả các khách du lịch đến thành phố thăm
quan trong cùng một chuyến đi. Lấy ví dụ: Về bản đồ gồm 7 thành phố, mỗi cạnh
được nối giữa các thành phố biểu thị những con đường và các số viết trên mỗi cạnh
cho biết cho biết giới hạn hành khách của dịch vụ xe buýt chạy trên tuyến đường
đó.
Bây giờ, nếu ông G muốn đưa 99 khách du lịch từ thành phố 1
đến thành phố 7. Ông ta sẽ phải yêu cầu ít nhất là 5 chuyến đi, và lộ trình ông
ta nên đi là 1 – 2 – 4 – 7.
Nhưng, Ông G. nhận thấy là thật khó để
tìm ra tất cả lộ trình tốt nhất để sao cho ông ta có thể đưa tất cả khách du lịch
đến thành phố thăm quan với số chuyến đi là nhỏ nhất. Do vậy mà ông ta cần sự
trợ giúp của các bạn.
Dữ liệu vào: từ tệp văn bản TOURIST.INP
- Dòng đầu tiên chứa hai số nguyên N (N ≤ 1000) và R mô tả lần
lượt số thành phố và số đường đi giữa các thành phố.
- R dòng tiếp theo, mỗi dòng chứa 3 số nguyên: C1, C2, P.
Trong đó C1, C2 mô tả lộ trình đường đi từ thành phố C1 đến thành phố C2 và P
(P > 1) là giới hạn lớn nhất có thể phục vụ của dịch vụ xe buýt giữa hai
thành phố.
Các thành phố được đánh dấu bằng một số nguyên từ 1 đến N.
Dòng thứ (R+1) chứa ba số nguyên S, D, T mô tả lần lượt thành phố khởi hành,
thành phố cần đến và số khách du lịch được phục vụ.
Kết quả ra: ghi vào tệp văn bản TOURIST.OUT
Ghi ra số lộ trình nhỏ nhất cần phải đi qua các thành phố thỏa
mãn yêu cầu đề bài.
Ví dụ:
TOURIST.INP
|
TOURIST.OUT
|
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
|
5
|
