Chắc chắn bạn sẽ gây tắc đường
Đề bài
Mô tả
Bạn phụ trách thiết kế một hệ thống điều phối giao thông tập trung tiên tiến dành cho ô tô thông minh. Mục tiêu là dùng thông tin toàn cục để hướng dẫn những người đi làm buổi sáng, những người phải lái xe từ ngoại ô vào trung tâm thành phố, đi đến trung tâm theo cách tốt nhất mà không bị tắc đường.
Đáng tiếc là những người đi làm đều thuộc đường và ích kỷ, nên bạn không thể bảo họ đi theo một tuyến mất nhiều thời gian hơn bình thường (nếu vậy họ sẽ phớt lờ chỉ dẫn của bạn). Bạn chỉ có thể thuyết phục họ đổi sang một tuyến khác nhanh bằng đúng như vậy.
Mạng lưới đường của thành phố gồm các giao lộ được nối với nhau bởi các con đường hai chiều với thời gian di chuyển khác nhau. Mỗi người bắt đầu ở một giao lộ nào đó (giao lộ xuất phát có thể khác nhau giữa những người). Tất cả đều kết thúc hành trình ở cùng một nơi: trung tâm thành phố, tức giao lộ . Nếu hai người cùng bắt đầu đi vào một con đường theo cùng một chiều tại cùng một thời điểm thì sẽ xảy ra tắc đường; bạn phải tránh điều này. Tuy nhiên, hai người được phép đi qua cùng một giao lộ cùng lúc, và được phép đi vào cùng một con đường tại hai thời điểm khác nhau.
Hãy xác định số lượng lớn nhất người đi làm có thể lái xe vào trung tâm mà không gây tắc đường, với điều kiện tất cả bắt đầu hành trình tại đúng cùng một thời điểm và không ai đi theo một tuyến không tối ưu (mỗi người được chọn đều phải đi theo một đường đi ngắn nhất từ giao lộ xuất phát của mình tới giao lộ ).
Hình dưới minh họa ví dụ thứ hai: số trên mỗi cạnh là thời gian đi qua con đường đó, nhãn cạnh mỗi đỉnh là số xe xuất phát ở đó.
graph weighted 4 4 1 2 5 1 3 4 4 2 5 4 3 6 label 1 1 xe label 4 4 xe path orange 4 3 1 path green 4 2 1
Một xe đã ở sẵn trung tâm. Trong bốn xe ở giao lộ , một xe có thể đi theo tuyến màu cam qua giao lộ , một xe khác đi theo tuyến màu xanh lá qua giao lộ (cả hai tuyến đều dài ). Hai xe còn lại không thể vào trung tâm mà không gây tắc đường. Vậy tối đa xe vào được trung tâm mà không tắc đường.
Dữ liệu vào
Dữ liệu gồm một test duy nhất. Dòng đầu tiên chứa ba số nguyên , và : là số giao lộ, là số con đường và là số người đi làm. Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , và mô tả một con đường: và là hai giao lộ phân biệt mà con đường nối, là thời gian đi hết con đường theo chiều nào cũng vậy. Dòng cuối cùng chứa số nguyên là các giao lộ xuất phát của những người đi làm.
Dữ liệu ra
In ra số lượng lớn nhất người đi làm có thể vào trung tâm mà không gây tắc đường.
Ràng buộc
- , , .
- , , . Giữa hai giao lộ có thể có nhiều con đường.
- Từ mọi giao lộ đều có thể đi tới trung tâm (giao lộ ).
- Các giao lộ xuất phát nằm trong khoảng ; nhiều người có thể xuất phát ở cùng một giao lộ, kể cả giao lộ .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 2 1 2 42 2 3 1 2 3 1 2 3 |
2 | Người ở giao lộ đi thẳng con đường từ thời điểm . Người ở giao lộ đi một trong hai con đường , rồi vào con đường ở thời điểm , khác thời điểm của người kia nên không tắc. |
| 4 4 5 1 2 5 1 3 4 4 2 5 4 3 6 4 4 4 4 1 |
3 | Ví dụ trong hình: người ở giao lộ đã tới nơi, hai trong bốn người ở giao lộ đi theo hai tuyến và . |
Bình luận