문제
**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 1) to the fields (located at node N) traveling along exactly K 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 N vertices (1≤N≤300) with N2 edges: one edge for every pair (i,j) for 1≤i,j≤N (note that there are N self loops). After each removal, output the minimum weight of any path from 1 to N that passes through exactly K (not necessarily distinct) edges (2≤K≤8). Note that after the i-th removal, the graph has N2−i edges left.
The weight of a path is defined as the sum of the weights of all of the edges on the path. Note that a path can contain multiple of the same edge and multiple of the same vertex, including vertices 1 and N.
[번역]
농부 존의 농장은 도로(간선)로 연결된 다양한 노드로 나타낼 수 있는 방향성이 있는 가중 그래프로 나타낼 수 있으며, 각 간선의 가중치는 도로를 따라 이동하는 데 필요한 시간입니다. 매일 Bessie는 정확히 K개의 도로를 따라 이동하여 필드(노드 N에 위치)로 이동하려고 하며 이러한 제약 하에서 가능한 빨리 필드에 도착하려고 합니다. 그러나 언젠가는 도로가 유지되지 않게 되고, 하나씩 고장 나면서 통행이 불가능해집니다. Bessie에게 도와주어 농장에서 필드로 향하는 최단 경로를 찾아보세요!
정식으로는 농장은 N개의 정점 (1≤N≤300)을 가진 완전 가중 방향 그래프로 시작합니다. N2개의 간선이 있으며 각 (i,j) 쌍에 대해 하나의 간선이 있습니다 (참고: 자체 루프가 N개 있습니다). 각 제거 후, 1에서 N까지의 K개의 (필수는 아님) 간선을 통과하는 어떤 경로의 최소 가중치를 출력하세요 (2≤K≤8). i번째 제거 후에 그래프에는 N2−i개의 간선이 남아 있습니다.
경로의 가중치는 경로상의 모든 간선의 가중치의 합으로 정의됩니다. 경로에는 동일한 간선 및 동일한 정점이 포함될 수 있습니다. 그 중에는 정점 1과 N도 포함됩니다.
입력
The first line contains N and K.
The next N lines contain N integers each. The j-th integer of i-th line is wij (1≤wij≤108).
Then N2 additional lines follow, each containing two integers i and j (1≤i,j≤N). Every pair of integers appears exactly once.
[번역]
첫 번째 줄에는 N과 K가 있습니다.
다음 N개의 줄에는 각각 N개의 정수가 있습니다. i번째 행의 j번째 정수는 wij입니다 (1≤wij≤10^8).
그런 다음 N2개의 추가 줄이 따라오며, 각각 두 정수 i와 j가 있습니다 (1≤i,j≤N). 모든 정수 쌍이 정확히 한 번씩 나타납니다.
출력
Exactly N2 lines, the minimum weight K-path after each removal. If no K-path exists then output −1.
[번역]
정확히 N2줄, 각 제거 후 최소 가중치 K-경로를 출력합니다. K-경로가 없으면 -1을 출력하세요
예제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.
[번역]
첫 번째 제거 후, 가장 짧은 4-경로는 다음과 같습니다:
1 -> 2 -> 3 -> 2 -> 3
두 번째 제거 후, 가장 짧은 4-경로는 다음과 같습니다:
1 -> 3 -> 2 -> 1 -> 3
세 번째 제거 후, 가장 짧은 4-경로는 다음과 같습니다:
1 -> 3 -> 3 -> 3 -> 3
여섯 번째 제거 후에는 더 이상 4-경로가 없습니다.