버스 여행

문제 설명

여행가 김순례는 노드크루왕국을 여행하고 있습니다. 노드크루왕국에는 총 n개의 도시가 있고 m개의 버스가 있습니다. m개의 버스는 각각 1번 도시부터 n번 도시 중 서로 다른 두 도시를 왕복하며 운행합니다.

도시들의 위치는 김순례의 출발 위치로부터 x 방향 (+x 방향 : 동쪽 / -x 방향 : 서쪽)과 y 방향 (+y 방향 : 북쪽 / -y 방향 : 남쪽)으로 각각 몇 m에 있는지 주어져 있습니다.

김순례는 버스를 이용해 도시를 오가거나 걸어서 이동할 수도 있습니다.
김순례가 현재 위치에서 가고 싶은 도시까지 가장 일찍 도착하는데 걸릴 예상 소요 시간을 반환하는 solution 함수를 작성하시오.

김순례가 가고 싶은 도시까지 이동하는데 걸리는 예상 소요 시간을 (분 단위) 소수점 아래 셋째 자리까지 버림하여 반환합니다.

김순례의 여행에는 다음과 같은 몇 가지 가정이 포함되어 있습니다.

1. 김순례는 1분에 100m를 걷습니다.
2. 버스는 출발지와 도착지를 제외한 중간에서 타고 내릴 수 없습니다.
3. 동서 방향으로 x만큼 남북 방향으로 y만큼 떨어진 두 도시 사이의 거리는 $\sqrt{x^2 + y^2 \mathstrut }$ 입니다.
4. 버스 타기 위해 대기하는 시간은 없습니다.

제한 사항

• cities는 1번 도시부터 n 번 도시까지 총 n개의 도시 정보가 주어집니다.

  • cities의 원소는 김순례의 출발 위치에서부터 'x 방향 떨어진 거리'와 'y 방향 떨어진 거리'로 이루어져 있습니다.
  • 도시의 개수 n은 2 이상 1,000 이하의 자연수입니다.
  • x, y는 -10,000(m) 에서 10,000(m) 사이의 실수이며, 소수점 아래 셋째자리까지 주어집니다.

• buses는 총 m 개의 버스 정보가 주어집니다.

  • buses는 왕복하는 출발 도시 번호(s)와 도착 도시 번호(e) 및 두 도시를 이동하는데 걸리는 시간(time, 분 단위)이 차례로 입력됩니다.
  • s와 e는 1 이상 n이하의 자연수입니다
  • m은 50,000 이하의 자연수입니다.
  • time은 1,000 이하의 자연수입니다.

• dest는 김순례가 가고 싶은 도시 번호가 주어집니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 1번 도시까지 걸어가는 데 0.145분이 소요됩니다. 그 이후 1번 도시에서 3번 도시로 버스를 타고 1분 동안 이동하면 1.145 분 만에 3번 도시로 이동할 수 있습니다.

2번 테스트케이스 설명

• 시작점에서 4번 도시까지 바로 걸어가면 1.022 분 만에 이동할 수 있습니다.