stdKonjac's Blog

 要做到不可替代,就要与众不同。

【Shortest】

【问题描述】

给定一张n个点的有向带权完全图,和一个数组a[],请按顺序删除数组中的点,请求出删除点a[i]之前,所有未删除点对之间的最短路上的值的和。

【输入格式】

第一行一个整数n,表示点数;

接下来n行,每行n个数构成邻接矩阵,描述每条边的权值,保证i号点到i号点的权值为0;

最后一行n个小于等于n的不同的数,描述数组a[]

【输出格式】

输出1行n个数,表示答案。

【输入样例】

4

0 3 1 1

6 0 400 1

2 4 0 1

1 1 1 0

4 1 2 3

【输出样例】

17 23 404 0

【数据范围】

对30%的输入数据:1≤n≤10

对100%的输入数据:1≤n≤500,权值≤100000

Floyed新技能get

正向思考很难,可以考虑逆向加点。对于每次加一个点,考虑从它出发的边能否更新旁边的点,把与它有关的所有边都扫一次进行更新。之后再跑一遍Floyed来更新整个图,时间复杂度为n³,更新的时候也只考虑用与它相连的点的最优解来更新其它距离。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.