출근길 순회
면접 대비시간 제한2초메모리 제한512 MB
가중 무방향 도시 그래프에서 사무실은 0번 교차점이고 직원 집이 최대 10곳 있을 때, 사무실에서 출발해 모든 집을 들른 뒤 사무실로 돌아오는 최단 경로의 길이를 구한다.
문제
Wajed는 소프트웨어 회사에서 운전기사로 일한다. 그는 직원들을 집에서 회사 본사까지 태워다 주는 일을 맡고 있다. 매일 그는 본사에서 출발해 모든 직원의 집을 들러 직원들을 태운 뒤 사무실로 데려간다. 시간과 연료를 아껴야 하므로 그는 가장 적은 비용으로 이 일을 처리할 최적의 경로를 찾으려 한다. 회사에서 출발해 모든 직원을 태우고 다시 회사 사무실로 돌아오는 가장 짧은 경로를 구하라.
입력
첫 줄에는 테스트 케이스의 수가 주어진다: 0 < T < 100.
이어지는 T개의 테스트 케이스는 각각 두 정수 N, M이 있는 줄로 시작한다. N은 교차로의 수(모두 0부터 N-1까지 번호가 매겨져 있다), M은 도시의 도로 수다. 회사는 0번 교차로에 있다. 다음 M개 줄에는 각각 세 정수 X, Y, D가 주어진다(0 <= X, Y, D <= 1000). 교차로 X와 Y가 길이 D인 양방향 도로로 연결되어 있다는 뜻이다. 그다음 줄에는 태워야 할 직원의 수 S(1 <= S <= 10)가 주어진다. 이어지는 S개 줄에는 각 직원의 집이 있는 교차로 번호가 하나씩 주어진다. 회사에서 모든 직원을 태울 수 있는 경우만 주어진다.
출력
각 테스트 케이스마다 회사에서 출발해 모든 직원을 태우고 회사로 돌아오는 가장 짧은 이동 거리를 정수 하나로 출력한다.