trang chủ / đề bài / icpcwf20_j

Tuyết không thành vấn đề

Đề bài

Mô tả

Học viện Kỹ thuật và Công nghệ Yllihc (YETI), nằm ở miền bắc xứ Snowblovia, có hai vấn đề: tuyết và tiền. Cụ thể là họ có quá nhiều thứ thứ nhất và không đủ thứ thứ hai. Mỗi mùa đông (và cả mùa thu lẫn mùa xuân) khuôn viên trường bị phủ kín bởi những lớp tuyết dày, và các vỉa hè nối các tòa nhà trong trường không thể đi lại được. Để tiếp tục hoạt động, YETI cần dọn tuyết trên các vỉa hè nối các tòa nhà. Vì ngân sách eo hẹp, các vỉa hè này là một tập tối thiểu đảm bảo giữa hai tòa nhà bất kỳ luôn có đường đi.

Với số tiền tiết kiệm được nhờ không xây thêm vỉa hè, YETI đã mua hai máy thổi tuyết. Để dọn tuyết, hai nhân viên đưa hai máy thổi tuyết ra khỏi tòa nhà (hoặc các tòa nhà) đang cất chúng và đẩy máy dọc theo các vỉa hè để dọn tuyết. Mỗi vỉa hè phải được đi qua ít nhất một lần. Mỗi máy thổi tuyết, sau khi dọn xong, được cất vào tòa nhà mà nó đang ở cạnh (và ở trận tuyết tiếp theo, các máy sẽ được đẩy theo chiều ngược lại, cứ thế suốt mười một tháng của mùa tuyết).

Đội bảo trì của YETI muốn chọn tòa nhà cất các máy thổi tuyết và thiết kế lộ trình đẩy từng máy sao cho tổng quãng đường hai máy phải đi ngoài trời lạnh là nhỏ nhất (để bảo vệ cả thiết bị quý giá lẫn nhân viên khỏi bị đóng băng). Lưu ý rằng lộ trình có thể đi qua cả những vỉa hè đã được dọn, như hình dưới đây minh họa một lời giải tối ưu cho Ví dụ 1: một máy đi 1→4→5→6 (màu xanh lam, dài 5), máy còn lại đi 2→4→3→4→5→7 (màu đỏ, dài 10).

graph weighted
7 6
1 4 2
2 4 3
3 4 1
4 5 1
5 6 2
5 7 4
path blue 1 4 5 6
path red 2 4 3
highlight red 5-7

YETI muốn nhờ Khoa Khoa học Máy tính giải quyết việc này, nhưng khoa đã bị xóa sổ trong Trận Bão Tuyết Lớn năm 2006, nên họ tìm đến bạn.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n, số tòa nhà trong khuôn viên YETI. Các tòa nhà được đánh số từ 1 đến n.

Mỗi dòng trong n−1 dòng tiếp theo chứa ba số nguyên a, b và d, cho biết có một vỉa hè độ dài d nối hai tòa nhà a và b.

Dữ liệu ra

In ra tổng quãng đường nhỏ nhất mà hai máy thổi tuyết phải đi để dọn tuyết trên mọi vỉa hè.

Ràng buộc

  • 4≤n≤100000.
  • 1≤a,b≤n, a≠b, 1≤d≤500.
  • Các vỉa hè nối mọi tòa nhà với nhau (giữa hai tòa nhà bất kỳ có đúng một đường đi).

Ví dụ

Input Output Giải thích
7
1 4 2
2 4 3
3 4 1
4 5 1
5 6 2
5 7 4
15 Như hình trên: lộ trình 1→4→5→6 dài 2+1+2=5 và lộ trình 2→4→3→4→5→7 dài 3+1+1+1+4=10, tổng 15.
4
1 2 1
2 3 2
3 4 3
6 Các vỉa hè tạo thành một đường thẳng 1−2−3−4: một máy đi từ 1 đến 4 (dài 6), máy còn lại không cần đi.

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