P8906 [USACO22DEC] Breakdown P

Farmer John’s farm can be represented as a weighted directed graph. Roads (edges) connect different nodes, and the weight of each edge is the time needed to travel along that road. Every day, Bessie likes to go from the barn (located at node $1$) to the pasture (located at node $N$) using exactly $K$ roads, and she wants to arrive as quickly as possible under this restriction. However, at certain times, roads stop being maintained and begin to break down one by one, becoming impassable. Help Bessie find the shortest path from the barn to the pasture at every moment. Formally, we start with a weighted directed complete graph with $N$ nodes ($1 \le N \le 300$) and $N^2$ edges: for every pair $(i,j)$ with $1 \le i,j \le N$, there is an edge (note that there are $N$ self-loops). After each removal of one edge, output the minimum total weight among all paths from $1$ to $N$ that use exactly $K$ edges (edges on the path do not have to be distinct) ($2 \le K \le 8$). Note that after the $i$-th removal, the graph has $N^2-i$ edges remaining. The weight of a path is defined as the sum of the weights of all edges on the path. Note that a path may contain the same edge multiple times or visit the same node multiple times, including nodes $1$ and $N$.

The first line contains $N$ and $K$. The next $N$ lines each contain $N$ integers. The $j$-th integer in the $i$-th line is $w_{ij}(1 \le w_{ij} \le 10^8)$. The following $N^2$ lines each contain two integers $i$ and $j$ ($1 \le i,j \le N$). Each pair of integers appears exactly once.

Output $N^2$ lines. For each edge removal, output the minimum total weight of a path that uses exactly $K$ edges. If no such path exists, output $-1$.

### Sample 1 Explanation After the first removal, the shortest path that uses exactly $4$ edges is: $$1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3$$ After the second removal, the shortest path that uses exactly $4$ edges is: $$1 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 3$$ After the third removal, the shortest path that uses exactly $4$ edges is: $$1 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3$$ After the sixth removal, there is no longer any path that uses exactly $4$ edges. ### Testdata Properties - For $2 \le T \le 14$, testdata $T$ satisfies $K=\lfloor \dfrac{T+3}{2} \rfloor$。 Translated by ChatGPT 5