#PU1260. USACO 2022 December Contest, Platinum — Problem 1. Breakdown
USACO 2022 December Contest, Platinum — Problem 1. Breakdown
USACO 2022 December Contest, Platinum — Problem 1. Breakdown
题目描述
Note: the time limit for this problem is 3s, 50% larger than the default. Farmer John's farm can be represented as a directed weighted graph, with roads (edges) connecting different nodes, and the weight of each edge being the time required to travel along the road. Every day, Bessie likes to travel from the barn (located at node ) to the fields (located at node ) traveling along exactly roads, and wants to reach the fields as quickly as possible under this constraint. However, at some point, the roads stop being maintained, and one by one, they start breaking down, becoming impassable. Help Bessie find the shortest path from the barn to the fields at all moments in time! Formally, we start with a complete weighted directed graph on vertices () with edges: one edge for every pair for (note that there are self loops). After each removal,
输入格式
The first line contains and . The next lines contain integers each. The -th integer of -th line is (). Then additional lines follow, each containing two integers and (). Every pair of integers appears exactly once.
输出格式
Exactly lines, the minimum weight -path after each removal. If no -path exists then output .
数据范围
For , test case satisfies . Problem credits: Benjamin Qi
样例
样例 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
After the first removal, the shortest $4$-path is:
1 -> 2 -> 3 -> 2 -> 3
After the second removal, the shortest $4$-path is:
1 -> 3 -> 2 -> 1 -> 3
After the third removal, the shortest $4$-path is:
1 -> 3 -> 3 -> 3 -> 3
After six removals, there is no longer a $4$-path.