24519번 - Bottleneck Travelling Salesman Problem (Large) 스페셜 저지

외판원 순회 문제는 영어로 Traveling Salesman Problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 이 중 변종 문제 중 하나인 Bottleneck Traveling Salesman Problem (BTSP) 문제를 살펴보자.

정점의 개수가 $N$개, 비용이 있는 간선이 $M$개인 방향 그래프가 주어진다. 어느 한 정점에서 출발해, 출발한 정점을 제외한 $N-1$개의 정점을 모두 한 번씩 방문하고 다시 처음 정점으로 돌아오는 순회를 찾으려고 한다. 이러한 순회는 여러 가지가 있을 수 있는데, 정점 간 이동 비용의 최댓값을 최소화하려고 한다.

그래프가 주어졌을 때, 정점 간 이동 비용의 최댓값을 최소화하면서 모든 정점을 방문하는 순회를 찾아보자.

첫 번째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($2 \le N \le 18$, $0 \le M \le N(N-1)$)

두 번째 줄부터 $M$개의 줄에 걸쳐서 간선에 대한 정보가 세 정수 $u$, $v$, $c$로 주어진다. 이는 정점 $u$에서 $v$로 향하는 비용이 $c$인 간선이 있음을 의미한다. 두 정점 사이에 같은 방향의 간선이 2개 이상 존재하지 않는다. ($1 \le u, v \le N$, $u \ne v$, $1 \le c \le 5 \, 000 \, 000$)

모든 정점을 방문하는 순회가 있다면 첫 번째 줄에 정점 간 이동 비용의 최댓값의 최솟값을 출력한다. 만약에 이러한 순회가 없는 경우 -1을 출력한다.

모든 정점을 방문하는 순회가 있다면, 다음 줄에 정점 간 이동 비용의 최댓값을 최소화하도록 방문해야 하는 정점 번호를 순서대로 $N$개를 출력한다. 이러한 순회가 여러 가지가 있는 경우 아무것이나 출력해도 된다.