Breakdown

题目描述

注意：本题时间限制为 3s，比默认值大 50%。 Farmer John 的农场可以表示为一个带权有向图，道路（边）连接不同的节点，每条边的权值表示沿该道路行走所需的时间。每天，Bessie 喜欢从谷仓（位于节点 $1$）到田地（位于节点 $N$），并且要求恰好走过 $K$ 条道路，同时希望在此约束下尽快到达田地。然而，在某个时刻，道路不再被维护，它们会一个接一个地损坏，变得无法通行。请帮助 Bessie 在所有时刻找出从谷仓到田地的最短路径！

形式化地说，我们从一个在 $N$ 个顶点上的完整带权有向图开始（$1\le N\le 300$），共有 $N^2$ 条边：对每一对 $(i, j)$（$1 \le i, j \le N$）都有一条边（注意有 $N$ 条自环）。每次移除一条边后，输出从 $1$ 到 $N$、恰好经过 $K$ 条（不一定互不相同）边的所有路径中最小的权值（$2\le K\le 8$）。注意在第 $i$ 次移除之后，图中还剩 $N^2-i$ 条边。

路径的权值定义为路径上所有边的权值之和。注意一条路径可以包含多次相同的边以及多次相同的顶点，包括顶点 $1$ 和 $N$。

输入格式

第一行包含 $N$ 和 $K$。 接下来 $N$ 行每行包含 $N$ 个整数。第 $i$ 行的第 $j$ 个整数为 $w_{ij}$（$1\le w_{ij}\le 10^8$）。 然后还有额外的 $N^2$ 行，每行包含两个整数 $i$ 和 $j$（$1\le i,j\le 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 移除 6 次后，不再存在 $4$-路径。 SCORING: 对 $2\le T\le 14$，测试点 $T$ 满足 $K=\lfloor (T+3)/2\rfloor$。 题目来源：Benjamin Qi

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum