trang chủ / đề bài / icpcwf16_i

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ừ 30 đến 60 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 50 kilômét thì thời gian của nó nằm trong khoảng từ 50 đến 100 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 n, số thành phố, được đánh số từ 0 đến n−1. Tiếp theo là n dòng, mỗi dòng chứa n 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ứ j trên dòng thứ i là quãng đường khi đi thẳng từ thành phố i đến thành phố j. Giá trị −1 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 0, mọi khoảng cách khác đều dương và không quá 1000. Có nhiều nhất 100 con đường.

Tiếp theo là một dòng chứa một số nguyên r, số chuyến giao đã thực hiện. Mỗi dòng trong r dòng tiếp theo chứa ba số nguyên s, d và t: s và d là thành phố xuất phát và thành phố đích, t là thời gian (phút) của chuyến giao từ s đến d.

Cuối cùng là một dòng chứa một số nguyên q, số truy vấn về các chuyến giao trong tương lai. Mỗi dòng trong q dòng tiếp theo chứa hai số nguyên s và d: 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 r+q 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á 10−6.

Ràng buộc

  • 1≤n≤30.
  • Mọi khoảng cách khác −1 và 0 là số nguyên dương không quá 1000; có nhiều nhất 100 con đường.
  • 1≤r≤100, 1≤q≤100.

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 0→2 đi qua 0→1→2 (dài 90km) mất 120 phút. Đường 0→1 mất ít nhất 50 phút, nên đường 1→2 mất nhiều nhất 70 phút; tương tự đường 0→1 mất nhiều nhất 120−40=80 phút. Đường 1→0 không xuất hiện trong chuyến nào nên chỉ biết thời gian nằm trong [55,110].
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 0→1→2→0. Mỗi chuyến đi qua hai con đường liên tiếp và mất 21 phút, nên tổng ba con đường là 31,5 phút và mỗi con đường mất đúng 10,5 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0