【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³,更新的时候也只考虑用与它相连的点的最优解来更新其它距离。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*