#G. Just delete vertex

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个 $n$ 个点的图，任意两点之间都连有且仅有一条边，将会进行以下操作 $n$ 次:

给出一个未被删除的点，然后将其删除。

请在每次删除点之前输出1号点到其他点的最短距离和。(数据保证1号点一定最后一个被删除)

第一行一个整数 $n(n\leq 500)$ 表示图中点的数量。

接下来 $n$ 行，每行 $n$ 个整数，第 $i(1\leq i \leq n)$ 行第 $j(1\leq j \leq n)$ 列的数字 $a_{ij}(a_{ij}\leq 10^5)$ 表示 $i$ 号点和 $j$ 号点之间所连边的长度。

接下来一行 $n$ 个数，其中第 $i$ 个数 $x_i$ 表示第 $i$ 次操作删除的点的编号。

输出一行包含 $n$ 数，第 $i$ 个数表示进行第 $i$ 次删除操作前1号点到其他点的最短距离和，每个数之间用一个空格分隔。

3 1 0

在删除3号点之前，1号点到自身的最短距离为0，到2号点的最短距离为1，到3号点的最短距离为2，总距离为3。

在删除2号点之前，1号点到自身的最短距离为0，到2号点的最短距离为1，总距离为1。