Thời gian đi đường
Đề bài
Mô tả
Ubol Narongdid là người sáng lập một công ty khởi nghiệp mới đầy tham vọng tên là Special D-Liver-E. Cô muốn chiếm lĩnh thị trường giao nội tạng qua đêm giữa các bệnh viện trong vùng Phuket. Để lập lịch, cần ước lượng chính xác thời gian thực hiện các chuyến giao như vậy. Một số chuyến giữa các bệnh viện đã được thực hiện, nên thời gian giao giữa những cặp bệnh viện đó đã biết. Công ty hiện có phần mềm ước lượng thời gian cho những chuyến khác (chưa từng đi), nhưng đến nay mọi ước lượng đều sai lệch thảm hại.
Bạn được giao nhiệm vụ tìm ra cách cải thiện các ước lượng này. Bạn có trong tay các thông tin sau: 1) độ dài (tính bằng kilômét) của các con đường nối các cặp thành phố trong vùng Phuket, và 2) thời gian (tính bằng phút) của một số chuyến giao đã thực hiện.
Bạn biết rằng các con đường đều là đường một chiều, và mỗi con đường có một giới hạn tốc độ cố định nằm trong khoảng từ đến kilômét/giờ. Giới hạn tốc độ là số thực, không nhất thiết là số nguyên. Bạn cũng biết rằng xe tải giao hàng luôn đi theo tuyến đường có tổng quãng đường nhỏ nhất, và trên mỗi con đường xe luôn chạy với tốc độ không đổi bằng đúng giới hạn tốc độ của con đường đó. Do đó, ví dụ, nếu một chuyến dài kilômét thì thời gian của nó nằm trong khoảng từ đến phút (tính cả hai đầu), khi không có thêm thông tin nào khác. Nhưng bạn có thêm thông tin: thời gian của các chuyến giao trước đó. Nhiệm vụ của bạn là dùng chúng để đưa ra ước lượng tốt nhất có thể.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số thành phố, được đánh số từ đến . Tiếp theo là dòng, mỗi dòng chứa số nguyên mô tả khoảng cách tính bằng kilômét giữa các thành phố: số thứ trên dòng thứ là quãng đường khi đi thẳng từ thành phố đến thành phố . Giá trị nghĩa là không có con đường trực tiếp nào nối hai thành phố đó, khoảng cách từ một thành phố đến chính nó luôn bằng , mọi khoảng cách khác đều dương và không quá . Có nhiều nhất con đường.
Tiếp theo là một dòng chứa một số nguyên , số chuyến giao đã thực hiện. Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , và : và là thành phố xuất phát và thành phố đích, là thời gian (phút) của chuyến giao từ đến .
Cuối cùng là một dòng chứa một số nguyên , số truy vấn về các chuyến giao trong tương lai. Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và : thành phố xuất phát và thành phố đích của truy vấn.
Dữ liệu đảm bảo với mỗi cặp xuất phát/đích trong cặp của dữ liệu vào, tuyến đường có tổng quãng đường nhỏ nhất là duy nhất.
Dữ liệu ra
Với mỗi truy vấn, in một dòng gồm thành phố xuất phát và thành phố đích của truy vấn đó, tiếp theo là cận dưới và cận trên tốt nhất của thời gian đi, với sai số tuyệt đối hoặc tương đối không quá .
Ràng buộc
- .
- Mọi khoảng cách khác và là số nguyên dương không quá ; có nhiều nhất con đường.
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 0 50 -1 55 0 40 -1 40 0 1 0 2 120 3 0 1 1 2 1 0 |
0 1 50.0 80.0 1 2 40.0 70.0 1 0 55.0 110.0 |
Chuyến đi qua (dài km) mất phút. Đường mất ít nhất phút, nên đường mất nhiều nhất phút; tương tự đường mất nhiều nhất phút. Đường không xuất hiện trong chuyến nào nên chỉ biết thời gian nằm trong . |
| 3 0 10 -1 -1 0 10 10 -1 0 3 0 2 21 1 0 21 2 1 21 3 0 1 1 2 2 0 |
0 1 10.500000000 10.500000000 1 2 10.500000000 10.500000000 2 0 10.500000000 10.500000000 |
Ba con đường tạo thành vòng . Mỗi chuyến đi qua hai con đường liên tiếp và mất phút, nên tổng ba con đường là phút và mỗi con đường mất đúng phút. |
Hình vẽ của ví dụ 1 (số trên cạnh là độ dài con đường):
graph directed weighted base=0 0 1 50 1 0 55 1 2 40 2 1 40
Bình luận