문제
바이트시의 경찰서에서는 치안 예방의 일환으로 새로운 민원봉사를 시행하기로 하였다.
N(1<= N <= 50)개의 교통이 불편한 지역에 사는 사람들의 귀가를 돕기로 한 것이다. 이 민원봉사를 위하여 2대의 경찰차를 배정하였다.
오늘은 민원봉사를 시작한 첫 날이다. M(1 <= M <= 15)개의 도움 신청이 들어왔다.
두 대의 경찰차가 경찰서를 출발하여 M개의 신청을 해결하고 다시 경찰서로 돌아오는 최소 이동 시간을 구하는 프로그램을 작성하시오.
입력
첫 행에 지역의 개수 N, 지역 사이 정보 개수 C(1 <= C < N*N), 도움 신청 수 M이 입력된다.
다음 행부터 C개의 행에 단방향 정보 si, ei, ti(si지역 출발하여 ei지역도착 할 때 이동시간 ti)가 입력된다.
다음 M개의 행에 hsi, hei(도움 요청 시작지역, 종료 지역)이 입력된다.(1 <= si, ei, hsi, hei <= N)
(1 <= ti <= 10,000)
출력
두 대의 경찰차가 경찰서를 출발하여 M개의 신청을 해결하고 다시 경찰서로 돌아오는 최소 이동 시간을 출력한다.
한 대의 경찰차는 한 번에 하나의 도움신청만 해결한다.
경찰서의 지역번호는 1번이고 도움을 해결하는 순서는 입력 순서가 아니어도 가능하다.
어떤 신청에 대하여 어느 경찰차가 움직여도 된다.
두 대의 경찰차는 동시에 움직일 수 있다.
입력데이터는 답이 반드시 존재하도록 주어진다.
예제
5 10 3
1 2 17
1 3 6
2 3 8
2 5 8
3 1 5
3 4 12
3 5 10
4 1 7
4 5 14
5 4 8
2 3
2 5
3 4
44
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.