Hành trình hỗn loạn
Đề bài
Mô tả
Hà Nội, thủ đô của Việt Nam, có giao lộ được nối với nhau bởi con đường hai chiều. Các giao lộ được đánh số từ đến , các con đường được đánh số từ đến . Con đường thứ nối giao lộ với giao lộ và có độ dài 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 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ị của các số nguyên từ đến , chi tiết theo ngày như sau:
- Ngày , kiện hàng được chuyển từ giao lộ đến giao lộ .
- Ngày , kiện hàng được chuyển từ giao lộ đến giao lộ .
- ...
- Ngày , kiện hàng được chuyển từ giao lộ đến giao lộ .
- ...
- Ngày , kiện hàng được chuyển từ giao lộ đến giao lộ .
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ị , 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ừ đến là một dãy giao lộ , trong đó mỗi cặp giao lộ liên tiếp đượ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 (): số bộ test. Mỗi bộ test gồm:
- Dòng đầu tiên chứa hai số nguyên và (; ): số giao lộ và số con đường.
- Dòng thứ trong dòng tiếp theo chứa ba số nguyên (; ) mô tả con đường thứ .
Dữ liệu đảm bảo:
- tổng trên tất cả các bộ test không vượt quá ,
- tổng trên tất cả các bộ test không vượt quá , 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ị 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
- ,
- ,
- Tổng và tổng trên tất cả các bộ test đều không vượt quá
- Đồ 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 , nên mỗi ngày có rủi ro . Bộ test thứ ba: mỗi ngày Tahp đều bắt kiện hàng đi qua con đường dài nối giao lộ và . Đá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à . Bộ test thứ hai: Mei không bao giờ cần dùng con đường dài ; rủi ro các ngày là . |
Bình luận