trang chủ / đề bài / icpcwf09_j

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 t giây của mỗi cặp ga kề nhau được ghi thành ⌊t/60⌋ phút hoặc ⌈t/60⌉ phút (nếu t chia hết cho 60 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 N là số ga tàu điện ngầm. Các ga được đánh số từ 1 tới N. Mỗi dòng trong N−1 dòng tiếp theo chứa ba số nguyên a, b và t, cho biết ga a và ga b kề nhau và đi giữa chúng mất 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ố 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test (bắt đầu từ 1) 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

  • 1≤N≤100.
  • 1≤a,b≤N, 1≤t≤300.
  • Mỗi file có không quá 200 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ố +20, −40, +20), mọi đường đi có sai số không quá 40 giây. Bộ test 3: mỗi cạnh có sai số +30 hoặc −30, 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ố −25, +38, −20, +20, −20 theo thứ tự các dòng; đường đi 2, 3, 5 có sai số 38+20=58. 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

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