Greg 与图

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个 $n$ 个顶点的完整有向带权图。游戏按排列 $x_1,x_2,\ldots,x_n$ 依次删除顶点；删除顶点时也删除与它关联的所有边。

在每次删除之前，求当前所有未删除顶点之间的最短路长度之和。求和对象是有序点对 $(u,v)$，包含 $u=v$（其贡献为 $0$）。最短路只能经过尚未删除的顶点。

输入格式

第一行包含 $n$。随后 $n$ 行给出邻接矩阵 $a$，最后一行给出删除排列 $x$。

输出格式

输出 $n$ 个整数，第 $i$ 个数表示删除 $x_i$ 之前的最短路总和。

样例输入 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

数据范围

$1\le n\le500$，$a_{ii}=0$，$1\le a_{ij}\le10^5$（$i\ne j$），$x$ 是 $1\ldots n$ 的排列。