H. 删点游戏

传统题

1000ms

256MiB

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

题目描述

给你一张简单有向图，我们要把所有点依次删完。光头强每次会删掉图中的一个点和所有与它相连的边，光头强想知道每删去一个点之后图中所有点对的距离之和。

图用以下形式给出：

第一行输入一个数 $n$ , 表示顶点数。

接下来 $n$ 行，会输入一个 $n∗n$ 的矩阵 $A$ 表示这张图的邻接矩阵，矩阵第 $i$ 行第 $j$ 列表示 $i$ 号顶点到 $j$ 号顶点有一条边权为 $A[i][j]$ 的边。

接下来一行，输入 $n$ 个数 $x_i$ ，代表删除顶点的次序。

你需要求出删除了第 0 个点（一个点都没删除）到第 $n−1$ 个点（图中还剩下一个点）时，图中所有点对的距离之和。

第一行一个整数 $n$ 。

接下来 $n$ 行，每行有 $n$ 个整数，表示邻接矩阵。

接下来一行， $n$ 个整数表示删除顶点的次序。

输出一行 $n$ 个数表示答案。

9 0

对于所有数据，保证 $2≤n≤300,1≤A[i][j]≤10000,A[i][i]=0,1≤x_i≤n,1≤i,j≤n$ 。