시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 379 | 148 | 119 | 39.404% |
상근이가 지배하는 나라에는 도시가 N개 있고, 도시는 M개의 양방향 도로로 연결되어 있다. 이 중 K개 도시에는 쇼핑몰이 있고, 국민은 도로를 통해서 쇼핑몰이 있는 마을로 가고, 쇼핑을 한다.
쇼핑몰이 멀리 떨어져 있는 사람은 쇼핑몰로 가기 위해 긴 시간 운전을 해야 한다. 상근이는 실정을 파악하기 위해서 쇼핑몰과 집의 최단 거리가 집의 위치에 따라서 어떻게 달라지는지 구하기로 한다. 집은 도시에 있을 수도 있고, 도로 위에 있을 수도 있다.
도로의 정보와 쇼핑몰이 있는 도시가 주어졌을 때, 쇼핑몰이 있는 도시와 가장 먼 거리에 있는 집까지의 거리를 구하는 프로그램을 작성하시오. 도시 속을 이동하는데 걸리는 시간은 0이다. 또, 사람들은 항상 최단 경로를 이용한다.
첫째 줄에 도시의 수 N, 도로의 수 M, 쇼핑몰이 있는 도시의 수 K가 주어진다. 도시는 1번부터 N번까지 번호가 매겨져 있다. (2 ≤ N ≤ 3000, 1 ≤ M ≤ 105, 1 ≤ K ≤ N)
다음 M개 줄에는 도로의 정보 a, b, l이 주어진다. a와 b를 잇는 도로의 길이가 l(1 ≤ l ≤ 1000)임을 의미하며, a와 b가 같은 경우는 없다. 두 도시 p와 q에 대해서, 두 도시를 잇는 도로는 2개 이상 존재하지 않는다. 항상 도로를 이용해서 모든 도시로 이동할 수 있다.
다음 K개 줄에는 쇼핑몰이 있는 도시의 번호가 주어진다. 한 도시에 쇼핑몰이 여러 개 있을 수는 없다.
쇼핑몰이 있는 곳에서 가장 멀리 떨어져 있는 집과의 거리(쇼핑몰과 집의 최단 거리의 최솟값)를 소수점 첫째자리에서 반올림해서 출력한다.
3 3 1 1 2 1 2 3 1 3 1 1 1
2
4 5 2 1 2 4 1 3 1 2 3 2 2 4 2 3 4 1 2 4
3
예제 1의 경우에 도로의 길이는 모두 1이고, 쇼핑몰은 1번 도시에만 있다. 쇼핑몰과 가장 먼 거리에 있는 집의 위치는 2번 도시와 3번 도시를 연결하는 도로에서 2번 도시와 거리가 0.5만큼 떨어져 있는 위치 위에 있는 곳이다. 이 집과 쇼핑몰의 거리는 1.5이다. 따라서, 반올림하면 2가 된다.
Olympiad > Japanese Olympiad in Informatics > JOI 2010/2011 3번