| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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 :))) |
