trang chủ / đề bài / icpc22_mn_i

Metro và xe buýt

Đề bài

Mô tả

Thành phố Hồ Chí Minh đã xây dựng một hệ thống metro. Hệ thống gồm n ga và m tuyến metro hai chiều. Tuyến thứ i nối hai ga ai và bi, có giá vé ci.

Biết rằng có thể đi từ một ga bất kỳ đến mọi ga khác (có thể phải chuyển tuyến), và giá của một lộ trình gồm nhiều tuyến liên tiếp bằng giá vé của tuyến đắt nhất trong đó. Cụ thể hơn, giá của lộ trình từ ga s1 đến ga sk với k−2 lần chuyển tuyến tại các ga s2,s3,…,sk−1 bằng giá lớn nhất trong các tuyến từ s1 đến s2, từ s2 đến s3, ..., từ sk−1 đến sk.

Hôm nay, chính quyền quyết định xây các tuyến xe buýt (cũng hai chiều) cho mọi cặp ga không được nối trực tiếp bằng tuyến metro. Như vậy, giữa mọi cặp ga có đúng một tuyến trực tiếp: hoặc metro, hoặc xe buýt.

Giá vé xe buýt được tính như sau: với mỗi cặp ga a và b được nối bằng tuyến xe buýt, giá của tuyến này bằng giá nhỏ nhất của một lộ trình metro từ a đến b theo cách tính giá ở trên.

Biết rằng chỉ dùng các tuyến xe buýt cũng có thể đi từ một ga bất kỳ đến mọi ga khác, và tương tự như metro, giá của một lộ trình gồm nhiều tuyến xe buýt bằng giá của tuyến đắt nhất trong đó.

Do sự cạnh tranh ngày càng tăng từ hệ thống xe buýt, ban quản lý metro đưa ra một cải cách và thay đổi giá vé các tuyến metro. Cụ thể, với tuyến metro thứ i nối hai ga ai và bi, giá mới của tuyến này bằng giá nhỏ nhất của một lộ trình xe buýt giữa hai ga ai và bi. Hãy giúp ban quản lý metro tính giá mới của các tuyến metro.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên chứa số nguyên t (1≤t≤104): số bộ test.

  • Dòng đầu tiên của mỗi bộ test chứa hai số nguyên n và m: số ga và số tuyến metro (4≤n≤2×105, n−1≤m≤2×105, m≤(n−1)(n−2)2).
  • Mỗi dòng trong m dòng tiếp theo chứa ba số nguyên ai, bi và ci (1≤ai,bi≤n, 1≤ci≤109): hai ga được nối bởi tuyến metro thứ i và giá vé của tuyến đó.

Dữ liệu đảm bảo không có tuyến nào nối một ga với chính nó, không có hai tuyến nối cùng một cặp ga, chỉ dùng metro có thể đi giữa mọi cặp ga, và chỉ dùng xe buýt cũng có thể đi giữa mọi cặp ga.

Gọi N là tổng các n và M là tổng các m của mọi bộ test. Dữ liệu đảm bảo N,M≤2×105.

Dữ liệu ra

Với mỗi bộ test, in ra trên một dòng m số nguyên, số thứ i là giá mới của tuyến metro thứ i sau cải cách.

Ràng buộc

  • 1≤t≤104
  • 4≤n≤2×105, n−1≤m≤2×105, m≤(n−1)(n−2)2
  • 1≤ci≤109
  • Tổng n và tổng m của mọi bộ test không vượt quá 2×105.

Ví dụ

Input Output Giải thích
3
4 3
1 2 1
2 3 2
4 3 3
5 5
1 2 1
1 3 1
2 4 1
4 5 2
5 1 3
6 6
1 2 3
2 3 1
3 6 5
3 4 2
4 5 4
2 4 2
3 3 3
1 1 1 2 2
4 4 5 3 4 4
Bộ test thứ nhất: các tuyến xe buýt là (1,3) giá 2 (lộ trình metro 1−2−3), (1,4) giá 3 và (2,4) giá 3. Sau cải cách, tuyến metro (1,2) có giá 3 (xe buýt 1−4−2), tuyến (2,3) có giá 3 (xe buýt 2−4−1−3), tuyến (3,4) có giá 3 (xe buýt 3−1−4). Bộ test thứ hai: các tuyến xe buýt là (1,4) giá 1, (2,3) giá 1, (2,5) giá 2, (3,4) giá 1, (3,5) giá 2.

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