传统题 1000ms 256MiB

Just delete vertex

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

Description

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

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

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

Input Format

第一行一个整数表示图中点的数量。

接下来n行,每行n个整数,第行第列的数字表示i号点和j号点之间所连边的长度。

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

Output Format

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

3
0 1 2
1 0 2
2 2 0
3 2 1​
3 1 0​

Hint

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

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

2023年第五届秋季校赛第二周训练预备赛

未参加
状态
已结束
规则
ACM/ICPC
题目
13
开始于
2023-11-19 13:30
结束于
2023-11-19 18:30
持续时间
5 小时
主持人
参赛人数
17