Ngày nay, việc thu phí đường bộ phát triển rất nhanh. Mật độ đường ngày càng lớn, do đó việc chọn lộ trình tốt nhất là một vấn đề thực tế. Đường trong thành phố là hai chiều, mỗi con đường có thời gian di chuyển cố định và chi phí cần thanh toán.
Một lộ trình là một chuỗi các con đường liên tiếp. Tổng thời gian là tổng thời gian của các con đường thành phần, tổng chi phí là tổng chi phí của các con đường đó. Một lộ trình càng nhanh hoặc chi phí càng thấp thì càng tốt. Cụ thể, nếu một lộ trình nhanh hơn các lộ trình khác và không tốn nhiều tiền hơn, nó được coi là tốt hơn. Ngược lại cũng vậy. Nếu không có lộ trình nào tốt hơn một lộ trình cụ thể, thì lộ trình đó được gọi là lộ trình tối ưu (minimal path).
Có thể có nhiều hơn một lộ trình tối ưu như vậy, hoặc hoàn toàn không tồn tại lộ trình nào.
Vấn đề: Đọc vào mạng lưới giao thông, tính tổng số lượng lộ trình tối ưu. Hai lộ trình tối ưu có cùng chi phí và thời gian chỉ được tính là một. Bạn chỉ cần xuất ra số lượng các loại lộ trình tối ưu khác nhau.
Dữ liệu:
Dòng đầu tiên có bốn số nguyên: tổng số thành phố , tổng số con đường , thành phố bắt đầu và thành phố kết thúc .
dòng tiếp theo, mỗi dòng mô tả thông tin một con đường gồm bốn số nguyên: hai đầu mút , chi phí , và thời gian .
Giữa hai thành phố có thể có nhiều đường nối.
Kết quả:
Một số duy nhất, biểu thị tổng số lượng các lộ trình tối ưu (khác nhau về cặp giá trị chi phí/thời gian).
