모이기 > 문제은행



알고리즘 최단거리

1855 : 모이기

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 12 회    시도횟수: 62 회   



1월 1일 연휴에 학원에 나오지 않은 학생들은 선생님들 몰래 같은 PC방에서 모여 LOL을 하고자 한다. 

그러나 모든 학생들이 게으르기로 유명한 학생들이고 서로 다른 곳에서 살고 있기 때문에 어디서 모여서 게임을 할지를 고민하고 있다.

그러던 도중에 가장 노는데 잔머리를 잘 굴리는 동욱이가 모든 학생의 이동시간의 합의 최소가 되는 지점에서 만나고자 제안을 했고, 

다른 학생들도 흔쾌히 동의를 하였다. 하지만 맨날 노는 데만 집중해서 공부를 소홀히 했던 학생들은 이 문제를 제대로 해결하지 못하고 

그나마 열심히 하는 축에 속하는 당신에게 프로그램을 짜달라고 요청하였다.

 

학생들이 사는 장소와 두 개의 장소를 잇는 경로의 이동시간이 주어지고 어떤 장소에서 모두 같이 모였을 경우, 

모든 학생의 이동 시간의 합의 최소를 구하는 프로그램을 작성하라.




입력의 첫 번째 줄에는 학생의 수 N(1≤N≤500), 장소의 수P(1≤P≤800), 그리고 장소를 잇는 경로의 수C(1≤C≤1,450)이 입력된다.

그 다음 줄부터 C개의 줄에는 3개의 정수 i, j, cost가 입력되는데 i번 장소와 j번 장소를 잇는 경로로 이동할 경우 cost만큼의 이동시간이 걸린다는 것이다. i번 장소에서 j번 장소로 이동하거나 j번 장소에서 i번 장소로 이동하는 것이 다 가능하다(1≤i, j≤P, 1≤cost≤225)

마지막으로 한 줄에는 N명의 학생이 현재 위치한 장소의 번호가 입력된다.




모든 학생들이 한 장소에 모였을 때 이동시간의 합의 최소를 출력한다.



3 4 5
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
2 3 4
8



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.