trang chủ / đề bài / icpc24_reg_j

Hành trình hỗn loạn

Đề bài

Mô tả

Hà Nội, thủ đô của Việt Nam, có n giao lộ được nối với nhau bởi m con đường hai chiều. Các giao lộ được đánh số từ 1 đến n, các con đường được đánh số từ 1 đến m. Con đường thứ i nối giao lộ ui với giao lộ vi và có độ dài wi km. Hệ thống đường đảm bảo có thể đi lại giữa hai giao lộ bất kỳ.

Tahp và Mei đang cạnh tranh một vị trí ở một công ty giao hàng. Để đánh giá năng lực của hai người, công ty đưa ra bài toán sau: có một kiện hàng cần được chuyển qua n giao lộ, mỗi giao lộ nhận kiện hàng đúng một lần, và các lần giao diễn ra vào các ngày khác nhau. Một cách hình thức, lịch giao hàng được biểu diễn bởi một hoán vị p của các số nguyên từ 1 đến n, chi tiết theo ngày như sau:

  • Ngày 1, kiện hàng được chuyển từ giao lộ p1 đến giao lộ p2.
  • Ngày 2, kiện hàng được chuyển từ giao lộ p2 đến giao lộ p3.
  • ...
  • Ngày i, kiện hàng được chuyển từ giao lộ pi đến giao lộ pi+1.
  • ...
  • Ngày n−1, kiện hàng được chuyển từ giao lộ pn−1 đến giao lộ pn.

Tuy nhiên, lịch giao hàng không cố định và có thể thay đổi trong quá trình thực hiện, vì vậy rủi ro khó dự đoán. Trong bài toán này, Tahp chịu trách nhiệm chọn hoán vị p, tức là thứ tự giao hàng. Sau đó Mei phải chọn tuyến đường giao hàng tối ưu cho từng ngày. Một tuyến đường từ u đến v là một dãy giao lộ u=x0,x1,…,xk=v, trong đó mỗi cặp giao lộ liên tiếp (xi,xi+1) được nối bởi một con đường. Mục tiêu của Tahp là làm rủi ro của lịch giao hàng lớn nhất, còn Mei muốn làm nó nhỏ nhất.

Công ty đánh giá rủi ro của lịch giao hàng theo các tiêu chí sau:

  • Rủi ro của một con đường là độ dài của nó.
  • Rủi ro của một tuyến đường là rủi ro lớn nhất trong các con đường trên tuyến đó.
  • Rủi ro của lịch giao hàng là tổng rủi ro của các tuyến đường giao hàng trong tất cả các ngày.

Hãy tìm rủi ro của lịch giao hàng và một lịch giao hàng đạt được rủi ro đó, giả sử cả Tahp và Mei đều chọn tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (1≤t≤5·105): số bộ test. Mỗi bộ test gồm:

  • Dòng đầu tiên chứa hai số nguyên n và m (2≤n≤5·105; n−1≤m≤5·105): số giao lộ và số con đường.
  • Dòng thứ j trong m dòng tiếp theo chứa ba số nguyên uj,vj,wj (1≤uj,vj≤n; 1≤wj≤109) mô tả con đường thứ j.

Dữ liệu đảm bảo:

  • tổng n trên tất cả các bộ test không vượt quá 5·105,
  • tổng m trên tất cả các bộ test không vượt quá 5·105, và
  • có thể đi lại giữa hai giao lộ bất kỳ bằng các con đường đã cho.

Dữ liệu ra

Với mỗi bộ test, in ra hai dòng:

  • Dòng thứ nhất chứa rủi ro của lịch giao hàng.
  • Dòng thứ hai chứa hoán vị p1,p2,…,pn mà Tahp đã chọn để đạt được rủi ro trên.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

  • 1≤t≤5·105
  • 2≤n≤5·105, n−1≤m≤5·105
  • 1≤uj,vj≤n, 1≤wj≤109
  • Tổng n và tổng m trên tất cả các bộ test đều không vượt quá 5·105
  • Đồ thị liên thông

Ví dụ

Input Output Giải thích
3
4 6
1 2 2
1 3 2
1 4 3
2 3 5
2 4 3
3 4 2
2 1
1 2 3
5 4
1 2 1
2 3 2
3 4 5
4 5 2
6
3 1 4 2
3
2 1
20
1 4 2 5 3
Bộ test thứ nhất: giữa hai giao lộ bất kỳ, Mei luôn đi được bằng các con đường dài 2, nên mỗi ngày có rủi ro 2. Bộ test thứ ba: mỗi ngày Tahp đều bắt kiện hàng đi qua con đường dài 5 nối giao lộ 3 và 4. Đáp án của đề gốc là 3 2 4 1, 2 1 và 2 4 1 5 3; mọi hoán vị đạt rủi ro lớn nhất đều được chấp nhận.
2
6 5
1 2 7
2 3 1
3 4 2
4 5 3
5 6 4
4 4
1 2 10
2 3 20
3 4 30
4 1 40
25
5 2 6 3 1 4
80
3 1 4 2
Bộ test thứ nhất: rủi ro các ngày là 3,4,4,7,7. Bộ test thứ hai: Mei không bao giờ cần dùng con đường dài 40; rủi ro các ngày là 20,30,30.

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