옛날 옛적 N개의 도시로 이루어진 한 나라가 있었다.

도시들은 도로로 연결되었으며 트리 구조를 이루었으며 1번 도시가 나라의 수도였다.

각 도시에는 전령들이 있어 도시에 긴급한 일이 생기면 이들이 수도로 메시지를 전달하는 역할을 한다.

메시지의 전달 방식은 다음과 같다.

우선 메시지가 출발하는 도시의 전령은 무조건 수도 방향으로 이동한다.

그러다가, 다른 도시에 도달하면 그 도시의 전령에게 메시지를 넘겨줄 수 있고 메시지를 받은 전령은 같은 방식으로 전달을 한다.

도시에 도착했다고 해서 무조건 메시지를 넘겨줄 필요는 없으며 한 명의 전령이 끝까지 메시지를 옮겨도 된다.

i번 도시의 전령이 움직이는 데는 출발 전의 준비에 S_i 분, 이동 시 1km당 V_i 분이 걸린다.

우리의 목적은 각 도시마다 해당 도시에서 출발해 수도로 메시지를 전달하는 최소시간을 계산하는 것이다.

전령들 timer 1s memory 128MB

전령들 1s 128MB