题目描述

C++ 选手请使用 GNU G++14 6.4.0 语言提交。

Greg 有一个有边权的有向图，包含 $n$ 个点。这个图的每两个点之间都有两个方向的边。Greg 喜欢用他的图玩游戏，现在他发明了一种新游戏：

• 游戏包含 $n$ 步。
• 第 $i$ 步 Greg 从图中删掉编号为 $x_i$ 的点。当删除一个点时，这个点的出边和入边都会被删除。
• 在执行每一步之前，Greg 想知道所有点对间最短路长度的和。最短路可以经过任何没删掉的点。换句话说，如果我们假设 $d(i, v, u)$ 是在删掉 $x_i$ 前 $v$ 和 $u$ 间的最短路长度，那么Greg想知道下面这个求和的值：$\sum_{v, u, v \neq u} d(i, v, u)$ 。

请你帮帮 Greg，输出每一步之前要求的值。

【简化版题意】

给定 $n$ 个点的有向图和一个排列，按照排列顺序删除有向图中的点，输出每次删除后两点间最短路之和。

输入格式

输出 $n$ 个整数，第 $i$ 个数等于游戏的第 $i$ 步之前统计的求和值。

请不要在 C++ 中使用 %lld 标志来输出 64 位整数 long long，推荐使用 cin, cout 流或者用 %I64d 标志。

输出格式

第一行包含一个整数 $n \ (1 \leq n \leq 500)$ ，代表图中的点数。

下面 $n$ 行每行包含 $n$ 个整数，代表边权：第 $i$ 行的第 $j$ 个数 $a_{ij} \ (1 \leq a_{ij} \leq 10^5, a_{ii} = 0)$ 代表从 $i$ 到 $j$ 的边权。

最后一行包含 $n$ 个整数：$x_1, x_2, \dots, x_n \ (1 \leq x_i \leq n)$ ，分别为Greg每一步删掉的点的编号。

1
0
1

2
0 5
4 0
1 2

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

0

9 0

17 23 404 0

翻译 By Luogu