Universal Cup Judging System

Universal Cup

Süre Sınırı: 1 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Có $n$ thành phố, được đánh số từ 1 đến $n$. Ngoài ra còn có $n - 1$ con đường hai chiều kết nối các thành phố này, sao cho với mọi cặp thành phố $x$ và $y$, luôn tồn tại một đường đi từ $x$ đến $y$. Con đường thứ $i$ nối thành phố $u_i$ và $v_i$, và có chi phí $c_i$. Mỗi lần đi qua con đường $i$, bạn phải trả $c_i$ đồng xu.

Hiện tại bạn đang ở thành phố 1 và muốn đi du lịch để thăm tất cả các thành phố. Mỗi giây, nếu đang ở thành phố $x$, bạn có thể chọn một thành phố $y$ được nối trực tiếp với thành phố $x$ bằng một con đường, di chuyển đến thành phố $y$ và trả chi phí của con đường tương ứng. Mỗi con đường chỉ có thể đi qua tối đa hai lần. Khi bạn đã thăm tất cả các thành phố và đang ở thành phố 1, bạn có thể kết thúc chuyến đi của mình. Chi phí của chuyến đi là tổng chi phí của tất cả các bước di chuyển mà bạn đã thực hiện.

Ngoài ra còn có một số nguyên $k$. Trong chuyến đi, bạn có thể sử dụng phiếu miễn phí một lần, giúp $k$ bước di chuyển tiếp theo của bạn không tốn chi phí.

Với mỗi $k$ từ 0 đến $2n - 2$, bạn cần tính chi phí nhỏ nhất của một chuyến đi thăm tất cả các thành phố và sử dụng phiếu miễn phí một cách tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 400$), số lượng bộ test. Với mỗi bộ test:

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 2000$), biểu thị số lượng thành phố.

$n - 1$ dòng tiếp theo mô tả các con đường. Dòng thứ $i$ trong các dòng này chứa ba số nguyên $u_i$, $v_i$ và $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), biểu thị các thành phố được nối bởi con đường thứ $i$ và chi phí của con đường đó.

Luôn có đường đi giữa mọi cặp thành phố. Tổng của $n$ không vượt quá $2000$.

Kết quả

Với mỗi bộ test, in ra một dòng chứa $2n - 1$ số nguyên: đáp án cho $k$ từ 0 đến $2n - 2$.

Ví dụ

Dữ liệu vào

2
5
1 2 2
2 3 3
2 4 1
4 5 3
7
1 2 1
1 3 1
1 4 4
3 5 5
3 6 1
6 7 4

Kết quả

18 15 12 10 8 5 3 2 0
32 27 22 21 17 13 12 8 4 3 2 1 0

Ghi chú

Ở bộ test đầu tiên, ta luôn có thể đi theo hành trình $1, 2, 3, 2, 4, 5, 4, 2, 1$ với dãy chi phí $2, 3, 3, 1, 3, 3, 1, 2$. Các đoạn được miễn phí ứng với mỗi $k$ đượcแสดง dưới đây.

$k$ đoạn miễn phí đáp án
0 $[]$ 18
1 $[3]$ 15
2 $[3, 3]$ 12
3 $[2, 3, 3]$ 10
4 $[3, 3, 1, 3]$ 8
5 $[3, 3, 1, 3, 3]$ 5
6 $[2, 3, 3, 1, 3, 3]$ 3
7 $[2, 3, 3, 1, 3, 3, 1]$ 2
8 $[2, 3, 3, 1, 3, 3, 1, 2]$ 0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.