Mở rộng mạng lưới

Buổi 67-68 — Mock IOI
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề bài

Cho đồ thị có hướng đầy đủ gồm $N$ đỉnh đánh số từ $1$ đến $N$. Trọng số cạnh trực tiếp từ $i$ đến $j$ là $w_{i, j}$ ($w_{i, i} = 0$).

Ban đầu tất cả các đỉnh đều bị khóa. Có $N$ bước mở khóa theo thứ tự hoán vị $p_1, p_2, \dots, p_N$. Ở bước thứ $t$, đỉnh $p_t$ được mở khóa. Sau bước thứ $t$, một đường đi hợp lệ chỉ được phép đi qua các đỉnh đã mở khóa. Hãy tính tổng độ dài đường đi ngắn nhất giữa tất cả các cặp có thứ tự $(u, v)$ của các đỉnh đã mở khóa.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 400$).
  • $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên mô tả ma trận $w_{i, j}$ ($0 \le w_{i, j} \le 10^6$, $w_{i, i} = 0$).
  • Dòng cuối cùng chứa $N$ số nguyên $p_1, p_2, \dots, p_N$ là một hoán vị của $1 \dots N$.

Kết quả

In ra $N$ số nguyên trên một dòng, số thứ $t$ là tổng độ dài đường đi ngắn nhất sau bước thứ $t$.

Subtasks

  • Subtask 1 (25%): $N \le 50$.
  • Subtask 2 (35%): $N \le 150$.
  • Subtask 3 (40%): Không có ràng buộc thêm.

Ví dụ

Input Output
3
0 1 5
2 0 1
5 3 0
2 1 3
0 3 14
Draft saved