두 로봇 |
---|
2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. <그림 1>은 방이 99개인 동굴 내부를간략하게 나타낸 예이다. <그림 1>에서 방은 원으로 표현되어 있으며 원 안의 수는 방 번호이다. 88개의 통로는 두 원 사이의 선분으로 표시되어 있으며 그 위의 정수 값이 통로의 길이이다. 예를 들어, 55번 방과 99번 방 사이에 길이가 66인 통로가 있음을 알 수 있다. 만약 두 로봇이 11번 방과 99번 방에 위치해 있다면, 각각 22번 방과 55번 방으로 이동한 후 통신할 수 있으며 이때 이동한 거리의 합은 1414로 최소이다. 동굴 내의 통로에 대한 정보와 두 로봇의 현재 위치가 입력으로 주어질 때, 서로 통신하기 위해 이동해야 하는 거리의 합의 최솟값을 계산하는 프로그램을 작성하시오. 동굴의 각 통로는 양 끝에 위치한 두 방의 번호와 그 길이로 주어진다. 두 로봇의 위치는 방 번호로 주어진다. |
입력 | |
---|---|
동굴의 방의 개수 NN과 두 로봇이 위치한 방의 번호가 세 개의 양의 정수로 공백으로 분리되어 첫 줄에 주어진다.
< 부분문제의 제약 조건 > 모든 부분문제에서 1 ≤ N ≤ 100,000이며, 통로의 길이는 1,000을 넘지 않는다.
|
출력 | |
---|---|
두 로봇이 서로 통신하기 위해 현재 위치에서 이동해야 하는 거리의 합의 최솟값을 정수로 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 5 1 5 1 2 1 2 3 2 3 4 3 4 5 4 | |
출력 | 6 | ||
2 | 입력 | 9 1 9 1 2 8 2 3 6 2 4 5 2 5 10 9 5 6 6 5 14 6 7 7 8 6 7 | |
출력 | 14 |
출처 | |
---|---|
2018년 한국정보올림피아드 전국 본선 초등부 3번 |