ABC338 F - Negative Traveling Salesman

Competitive Programming C++

2024-01-29

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc338/tasks/abc338_f

원문 링크
https://atcoder.jp/contests/abc338/editorial/9170

정점 \(i\)부터 \(j\)까지의 최단 경로의 길이를 \(d_{i, j}\)라고 합시다.
이 때, 답은 \((1, 2, …, N)\)의 순열 \(p_1, p_2, …, p_n\) 전부에 대한 \(d_{p_1, p_2} + d_{p_2, p_3} + … + d_{p_{N - 1}, p_N}\)의 최솟값이 됩니다.

증명

\(p_1\)부터 \(p_2\)까지의 최단 경로, \(p_2\)부터 \(p_3\)까지의 최단 경로, …, \(p_{N - 1}\)부터 \(p_N\)까지의 최단 경로를 이 순서대로 이어서 할 수 있는 순회가 조건을 만족한다는 것은 명백하므로, 반대로 조건을 만족하는 것들 중에서 지나가는 간선의 가중치의 합이 최소인 순회(이하 최적해)이고 앞서 말한 형태로 나타나는 것이 존재함을 보이면 됩니다.

최적해를 순회 \(x_1 \rightarrow x_2 \rightarrow .. \rightarrow x_k\)라 둡시다. 이 때, \(x_1 \neq x_k\)라 가정해도 됩니다. (\(x_1 = x_k\)일 때 경로 전체가 \(1\)개의 사이클이 되지만, 음의 사이클이 없는 것으로부터 가중치가 음이 아닌 간선을 \(1\)개 고를 수 있으므로, 이 간선을 삭제하고 사이클을 “펼치는” 것으로, 지나가는 정점의 집합을 그대로 둔 채로 지나가는 간선의 가중치의 합을 증가시키지 않고 사이클이 아닌 순회를 할 수 있습니다.)
따라서 \(x_1, x_2, …, x_k\)중에서 \(x_1\)과 \(x_k\)를 포함하는 \(N\)개의 점점을 중복 없이(즉 \(1, 2, …, N\)이 1번씩만 등장하도록) 고를 수 있습니다. 여기서 고르지 않은 부분에 대해서는 고른 정점들 중 가장 가까운 \(2\)개 정점의 최단 경로를 통해 잇는 것이 최적이 되는 것이 명백한 것으로부터, 이 순회는 위에서 설명한 형태가 됩니다.

다음과 같은 dp를 생각할 수 있습니다.

• \(\mathrm{dp}[S][i]\): 임의의 정점으로부터 시작해 정점 \(i\)에서 끝나는 순회 중 지나는 정점의 집합이 \(S\)인 것들에 대해서, 지나가는 간선의 가중치의 합의 최솟값

전이식은 아직 방문하지 않은 정점들 중 다음으로 방문할 정점 \(j\)를 완전 탐색하여, \(\mathrm{dp}[S \cup \{j\}][j] \leftarrow \min\{\mathrm{dp}[S \cup \{j\}][j], \mathrm{dp}[S][i] + d_{i, j}\}\)라 두면 됩니다.

따라서 플로이드-워셜 알고리즘 등을 이용해 모든 \(i, j\)쌍에 대해 \(d_{i, j}\)를 전처리해두는 것으로, 전체 \(O(N^3 + 2^NN^2)\)같은 시간복잡도에 풀 수 있습니다.

쫄아서 못푼거 같다.

F치고는 쉬운 난이도. 간단한 구현이었던거 같은데…
D에서 너무 많은 고민을 한 나머지 제대로 보지도 못했다.

더 잘 해야지 뭐.