#5932
도시 순회
1번부터 16번까지 번호가 붙은 16개의 도시가 있다. 서로 다른 두 도시 사이에는 도로가 하나씩 있어 완전 그래프를 이룬다.
그중 아래 그림에 표시된 15개의 도로는 하나의 트리를 이루며, 각 도로의 이동 시간은 그림에 적힌 값이다.
그림에 표시되지 않은 나머지 도로의 이동 시간은 모두 6이다.
모든 도시를 정확히 한 번씩 방문하는 경로의 총 이동 시간의 최솟값을 구하라. 경로의 시작 도시와 끝 도시는 자유롭게 고를 수 있다.
문제를 해결하려면 로그인해 주세요.
