Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P146SUME - ROUND 6E - Xóa đỉnh

Tí có một đồ thị có hướng, có trọng số gồm n đỉnh. Giữa 2 đỉnh luôn có 2 đường đi.

Giờ cậu muốn chơi một trò chơi như sau:

Trò chơi của cậu gồm n bước, tại bước thứ i cậu sẽ xóa khỏi đồ thị đỉnh x[i]. Khi loại bỏ đỉnh x[i] cậu cũng bỏ luôn tất cả các cạnh vào, ra từ đỉnh này nhưng trước khi thực hiện bước này, cậu muốn biết tổng độ dài đường đi ngắn nhất giữa 2 cặp đỉnh bất kì trong tất cả các đỉnh còn lại. Đường đi từ đỉnh i đến j coi là khác đường đi từ j đến i.

Các bạn giúp Tí tính nhé!

Input

Dòng đầu tiên là số nguyên n (1 <=n <= 500), số đỉnh của đồ thị.

n dòng tiếp theo, mỗi dòng gồm n số: Số thứ j của dòng i là a[i][j] (1 <= a[i][j] <= 10^5, a[i][i] = 0), trọng số của cung (i, j) (hướng từ đỉnh i đến đỉnh j).

n dòng tiếp, lần lượt là thứ tự các đỉnh bị xóa x[1], x[2], …, x[n] (1 <= x[i] <=n, 1 <=i <= n).

Output

In ra n số trên một dòng, số thứ i là kết quả của bước i.

Example

Test 1:

Input:

1

0

1

Output:

0

 

Test 2:

Input:

2

0 5

4 0

1 2

Output:

9 0

 

Test 3:

Input:

4

0 3 1 1

6 0 400 1

2 4 0 1

1 1 1 0

4 1 2 3

Output:

17 23 404 0


Được gửi lên bởi:adm
Ngày:2014-07-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2024-02-07 13:29:41
Time out
2014-09-22 15:45:24 Con Bò Huyền Thoại
làm sao để ko bị TLE :)))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.