당일치기 전주 여행 1

문제 배경

아침에 기차를 타고 전주역으로 이동한 후 전주 시내에 있는 5개의 관광지들을 돌아보고, 기차를 타고 집으로 돌아오는 당일치기 전주 여행을 계획하고 있다. 전주역에서 시작하여 모든 관광지를 모두 한 번씩 방문해야 한다.

문제

전주역과 5개의 관광지, 총 6개의 장소가 있다. 6×6 이동 시간 행렬이 주어질 때, 전주역에서 출발하여 5개 관광지를 모두 방문하고 전주역으로 돌아오는 최적 경로를 찾아, 이동 시간을 제외한 최대 체류 시간을 구하시오.