Thời gian tàu điện ngầm
Đề bài
Mô tả
Giống như hầu hết các thành phố hiện đại, Stockholm có một hệ thống giao thông công cộng phát triển. Trung tâm của giao thông công cộng ở Stockholm là tàu điện ngầm. Một bản đồ tô pô của hệ thống tàu điện ngầm thể hiện các tuyến tàu khác nhau và cách chúng nối với nhau, như minh họa trong Hình 1. Trong bài này, bạn hãy giả sử rằng bản đồ tàu điện ngầm luôn có dạng cây, dù điều này không hoàn toàn đúng với Stockholm vì chu trình tạo bởi tuyến xanh lá và tuyến xanh dương.

Hình 1: Bản đồ tàu điện ngầm Stockholm
Một bản đồ tô pô cho biết rất ít về hình học của hệ thống tàu điện ngầm, chẳng hạn khoảng cách (và do đó thời gian di chuyển) giữa các ga. Ví dụ, như hầu hết sinh viên ở Stockholm đều biết, khoảng cách giữa ga "Tekniska Högskolan" (Viện Công nghệ Hoàng gia) và ga "Universitetet" (Đại học Stockholm) khá lớn, dù bản đồ không hề cho thấy điều đó.
Bạn phải viết chương trình bổ sung cho bản đồ tô pô bằng cách ghi thời gian cần để đi giữa mọi cặp ga kề nhau. May mắn là các thời gian di chuyển này đã được biết, nên bạn không phải tự đo. Tuy nhiên, thời gian thực tế được cho theo giây, còn trên bản đồ phải ghi các giá trị ước lượng là số nguyên phút.
Một cách ước lượng tự nhiên là làm tròn mọi thời gian di chuyển tới phút gần nhất. Tuy nhiên, cách này có thể gây sai số tích lũy rất lớn. Chẳng hạn, trên bản đồ Stockholm, cách ước lượng này có thể dẫn tới sai số lên tới 15 phút trên tổng thời gian đi giữa một cặp ga nào đó. Để tránh điều này, chương trình của bạn được chọn làm tròn lên một số thời gian và làm tròn xuống một số thời gian khác. Việc làm tròn phải được thực hiện sao cho sai số tích lũy lớn nhất giữa một cặp ga bất kỳ là nhỏ nhất.
Nói cách khác: thời gian giây của mỗi cặp ga kề nhau được ghi thành phút hoặc phút (nếu chia hết cho thì hai cách như nhau). Sai số tích lũy giữa hai ga là trị tuyệt đối của hiệu giữa tổng thời gian đã ghi (đổi ra giây) và tổng thời gian thực tế trên đường đi duy nhất nối hai ga đó.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng số nguyên là số ga tàu điện ngầm. Các ga được đánh số từ tới . Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , và , cho biết ga và ga kề nhau và đi giữa chúng mất giây. Để đơn giản, bỏ qua thời gian tàu dừng ở ga. Các cặp ga kề nhau tạo thành một cây.
Sau bộ test cuối cùng là một dòng chứa số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test (bắt đầu từ ) rồi tới sai số làm tròn lớn nhất, tính bằng giây, của thời gian đi giữa hai ga bất kỳ khi thời gian giữa các cặp ga kề nhau được làm tròn một cách tối ưu. Theo đúng định dạng của ví dụ.
Ràng buộc
- .
- , .
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 1 2 110 4 1 2 40 2 3 40 3 4 40 4 1 2 90 1 3 90 1 4 90 0 |
Case 1: 10 Case 2: 40 Case 3: 60 |
Bộ test 1: làm tròn 110 giây lên 2 phút, sai số 10 giây. Bộ test 2: làm tròn lên, xuống, lên (sai số , , ), mọi đường đi có sai số không quá 40 giây. Bộ test 3: mỗi cạnh có sai số hoặc , luôn có hai cạnh cùng dấu tạo thành đường đi sai số 60 giây. |
| 1 3 1 2 120 2 3 300 6 1 2 25 2 3 22 3 4 140 3 5 40 2 6 140 0 |
Case 1: 0 Case 2: 0 Case 3: 58 |
Bộ test 1: chỉ có một ga. Bộ test 2: các thời gian chia hết cho 60 nên không có sai số. Bộ test 3: cách tối ưu duy nhất là sai số , , , , theo thứ tự các dòng; đường đi 2, 3, 5 có sai số . Làm tròn tới phút gần nhất cho sai số 67 trên đường đi 1, 2, 3, 4. |
Bình luận