P7032: 边权
传统题
3.000s
时间限制
512MB
内存限制
1 提交
0 解决
【题目描述】
【题目描述】
**
注意：本题的时间限制为 3 秒，比通常限制高 50%。**
Farmer John
的农场可以用一个带权有向图表示，道路（边）连接不同的结点，每条边的权值是通过道路所需的时间。每天，Bessie 喜欢从牛棚（位于结点 1）经过恰好 K
条道路前往草地（位于结点 N），并希望在此限制下尽快到达草地。然而，在某些时候，道路停止维护，一条一条地开始破损，变得无法通行。帮助 Bessie
求出每一时刻从牛棚到草地的最短路径！
形式化地说，我们从一个 N
个结点（1≤N≤300）和 N
^2
条边的带权有向完全图开始：对于 1≤i,j≤N 的每一对 (i,j) 存在一条边（注意存在 N 个自环）。每次移除一条边后，输出从 1 到 N 的所有路径中经过恰好 K 条边（不一定各不相同）的路径的最小权值（2≤K≤8）。注意在第 i
次移除后，该图还剩下N^2−i
条边。
路径的权值定义为路径上所有边的权值之和。注意一条路径可以包含同一条边多次或同一个结点多次，包括结点 1
和 N。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
和 K。
以下 N
行每行包含 N 个整数。第 i
行的第 j 个整数为 wij（1≤wij≤10
^8
）。
以下 N
^2
行，每行包含两个整数 i 和 j（1≤i,j≤N
）。每对整数出现恰好一次。
【
输出格式】
（输出至终端 /
标准输出）：
输出 N
^2
行，为每一次移除后经过 K 条边的路径的最小权值。如果不存在经过 K 条边的路径则输出 −1。
【
输入样例】
：
3 4
10 4 4
9 5 3
2 1 6
3 1
2 3
2 1
3 2
2 2
1 3
3 3
1 1
1 2
【
输出样例】
：
11
18
22
22
22
-1
-1
-1
-1
【样例说明】
第一次移除后，最短的经过 4
条边的路径为：
1 -> 2 -> 3 -> 2 -> 3
第二次移除后，最短的经过 4
条边的路径为：
1 -> 3 -> 2 -> 1 -> 3
第三次移除后，最短的经过 4
条边的路径为：
1 -> 3 -> 3 -> 3 -> 3
六次移除后，不再存在经过 4
条边的路径。
【
测试点性质】
：
对于2≤T≤14
，测试点 T
满足 K=⌊(T+3)/2⌋。