시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 426 | 206 | 152 | 52.055% |
외판원 순회 문제는 영어로 Traveling Salesman Problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 이 중 변종 문제 중 하나인 Bottleneck Traveling Salesman Problem (BTSP) 문제를 살펴보자.
정점의 개수가 $N$개, 비용이 있는 간선이 $M$개인 방향 그래프가 주어진다. 어느 한 정점에서 출발해, 출발한 정점을 제외한 $N-1$개의 정점을 모두 한 번씩 방문하고 다시 처음 정점으로 돌아오는 순회를 찾으려고 한다. 이러한 순회는 여러 가지가 있을 수 있는데, 정점 간 이동 비용의 최댓값을 최소화하려고 한다.
그래프가 주어졌을 때, 정점 간 이동 비용의 최댓값을 최소화하면서 모든 정점을 방문하는 순회를 찾아보자.
첫 번째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($2 \le N \le 9$, $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$개를 출력한다. 이러한 순회가 여러 가지가 있는 경우 아무것이나 출력해도 된다.
3 6 1 2 4 2 3 4 3 1 4 1 3 2 3 2 3 2 1 5
4 1 2 3
2 1 1 2 3
-1