← 返回题目列表

Codeforces · 295/B

B. 格雷格和图夫

中文机器翻译题面 查看原题

Greg 有一个加权有向图,由 n 个顶点组成。在此图中,任何一对不同的顶点在两个方向上都有一条边。格雷格喜欢玩图表,现在他发明了一个新游戏:

- 游戏由 n 个步骤组成。
- 在第 i 步中,Greg 从图中删除了顶点编号 xi。当 Greg 删除一个顶点时,他还删除了进出该顶点的所有边。
- 在执行每个步骤之前,Greg 想知道所有剩余顶点对之间的最短路径的长度总和。最短路径可以通过任何剩余的顶点。换句话说,如果我们假设 d(i, v, u) 是删除顶点 xi 之前形成的图中顶点 v 和 u 之间的最短路径,那么 Greg 想知道以下总和的值:$$\sum_{v,u,v\neq u} d(i,v,u)$$。

帮助Greg,在每一步之前打印所需总和的值。

输入

第一行包含整数 n (1 ≤ n ≤ 500) — 图中的顶点数。

接下来的 n 行每行包含 n 个整数 - 图邻接矩阵:第 i 行中的第 j 个数字 aij (1 ≤ aij ≤ 105, aii = 0) 表示从顶点 i 到顶点 j 的边的权重。

下一行包含 n 个不同的整数:x1, x2, ..., xn (1 ≤ xi ≤ n) — Greg 删除的顶点。

输出

打印 n 个整数 — 第 i 个数字等于第 i 步之前所需的总和。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 %I64d 说明符的 cin、cout 流。

示例

输入 #1

1
0
1

输出 #1

0

输入 #2

2
0 5
4 0
1 2

输出 #2

9 0

输入 #3

4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3

输出 #3

17 23 404 0