레이팅 미적용*참고: 이 문제의 시간 제한은 3초로, 기본값보다 50% 크다.*
농부 존의 농장은 방향 가중치 그래프로 나타낼 수 있다. 도로(간선)가 서로 다른 노드를 연결하며, 각 간선의 가중치는 그 도로를 지나는 데 걸리는 시간이다. 매일 베시는 헛간(노드 \(1\))에서 들판(노드 \(N\))까지 정확히 \(K\)개의 도로를 지나며 이동하는 것을 좋아하고, 이 제약 아래에서 가능한 한 빨리 들판에 도착하고 싶어 한다. 그런데 어느 시점부터 도로가 관리되지 않아, 하나씩 무너져 지나갈 수 없게 된다. 매 순간마다 헛간에서 들판까지의 최단 경로를 찾도록 베시를 도와주자!
형식적으로, \(N\)개의 정점(\(1\le N\le 300\))과 \(N^2\)개의 간선을 가진 완전 가중치 방향 그래프에서 시작한다. \(1 \le i, j \le N\)인 모든 쌍 \((i, j)\)마다 간선이 하나씩 있다 (자기 자신으로 가는 루프가 \(N\)개 있음에 유의한다). 각 간선이 제거될 때마다, 정확히 \(K\)개(서로 다를 필요는 없다)의 간선을 지나는 \(1\)에서 \(N\)까지의 경로의 최소 가중치를 출력한다 (\(2\le K\le 8\)). \(i\)번째 제거 후에는 그래프에 \(N^2-i\)개의 간선이 남아 있음에 유의한다.
경로의 가중치는 경로 위의 모든 간선의 가중치의 합으로 정의된다. 경로는 같은 간선과 같은 정점을 여러 번 포함할 수 있으며, 정점 \(1\)과 \(N\)도 여러 번 포함할 수 있음에 유의한다.
Problem credits: Benjamin Qi
채점 방식
- \(2\le T\le 14\)인 테스트 케이스 \(T\)는 \(K=\lfloor (T+3)/2\rfloor\)를 만족한다.
Problem credits: Benjamin Qi
첫째 줄에 \(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 211
18
22
22
22
-1
-1
-1
-1After 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.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Platinum