시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 1024 MB | 1920 | 736 | 515 | 35.298% |
$N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들이 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다.
이때, 가장 먼 곳은 선택할 집에서 거리가 가장 가까운 친구의 집까지의 거리를 기준으로 거리가 가장 먼 곳을 의미한다.
예를 들어, $X$ 위치에 있는 집에서 친구 $A$, $B$, $C$의 집까지의 거리가 각각 3, 5, 4이라 가정하고 $Y$ 위치에 있는 집에서 친구 $A$, $B$, $C$의 집까지의 거리가 각각 5, 7, 2라고 하자.
이때, 친구들의 집으로부터 땅 $X$와 땅 $Y$ 중 더 먼 곳은 땅 $X$이다. 왜냐하면 $X$에서 가장 가까운 친구의 집까지의 거리는 3이고, $Y$에서는 $2$이기 때문이다.
친구들이 살고 있는 집으로부터 가장 먼 곳을 구해보자.
첫번째 줄에 자취할 땅 후보의 개수 $N$이 주어진다.
2번째 줄에는 친구 $A$, $B$, $C$가 사는 위치가 공백으로 구분되어 주어진다. 이때 친구들은 $N$개의 땅 중 하나에 사는 것이 보장된다. (같은 위치에서 살 수 있다.)
3번째 줄에는 땅과 땅 사이를 잇는 도로의 개수 $M$이 주어진다.
그 다음줄부터 $M + 3$번째 줄까지 땅 $D$, 땅 $E$, 땅 $D$와 땅 $E$와 사이를 연결하는 도로의 길이 $L$이 공백으로 구분되어 주어진다. 이 도로는 양뱡항 통행이 가능하다.
친구들이 살고 있는 집으로부터 가장 먼 곳의 땅 번호를 출력한다. 만약 가장 먼 곳이 여러 곳이라면 번호가 가장 작은 땅의 번호를 출력한다.
6 1 2 5 8 1 2 1 2 3 4 1 4 2 2 5 3 1 6 5 5 6 2 3 4 2 4 5 6
3