세일즈맨이 N개의 도시를 방문하여 업무를 수행하고자 한다. 각 도시는 0번 부터 N-1번까지 번호가 메겨져 있으며, 각 도시를 적어도 한번 이상 방문을 하려고 한다. 세일즈맨은 0번 도시에서 시작하여 어떤 도시던 마지막 방문지로 정할 수 있다.

도시들 사이에는 M개의 서로 다른 두개의 도시를 잇는 양방향 도로가 있으며, 각 도로를 이용하기 위해서는 통행 요금을 내야 한다.

세일즈맨은 타임머신을 가지고 있는데, 타임머신을 이용하여 과거에 방문했던 도시로 아무런 비용없이 돌아갈 수 있다. 또한 타임머신을 쓸 경우 시간은 소요되지 않으며, 현재의 시간이 유지된다.

예를 들어 0, 1, 2, 3, 4 순으로 도시를 방문했을 때, 현재 세일즈맨은 현재 4번 도시에 위치해 있다. 여기서 타임머신을 쓸 경우 0, 1, 2, 3, 4 중 한곳으로 돌아갈 수 있다. 만약 2번 도시로 돌아 갔을 때, 그 다음에는 0, 1번 도시로만 돌아갈 수 있고, 3, 4번 도시로는 돌아가지 못한다. 타임머신을 사용하였을 경우 시간을 완전히 거슬러 가는 것이 아니기 때문에 이미 방문했던 곳은 방문 했던 곳으로 간주하게 된다. 따라서 5번에서 2번으로 타임머신을 써서 이동을 했을 경우에도 0, 1, 2, 3, 4번 도시를 방문한것으로 인정된다.

도시의 수와 각 도로의 정보가 주어졌을 때 0번 도시에서 시작하여 모든 도시를 적어도 한번 이상 방문하기 위한 통행 요금의 최소 합을 구하는 프로그램을 작성하라.

#2388 upload 19 done 10 how_to_reg 5

시간을 달리는 세일즈맨 timer 1s memory - MB

#2388

시간을 달리는 세일즈맨 1s - MB