시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1189 | 277 | 208 | 22.584% |
옛날 옛날에, 아름다운 몰다비아의 지역에 1부터 N까지 고유한 번호가 붙여진 N개의 중세 도시가 있었다. 번호 1이 붙여진 도시는 수도이다. 도시들은 N-1개의 양방향 도로로 연결되어 있으며, 각 도로는 킬로미터 단위의 길이를 가지고 있다.
도시를 두 번 거치지 않고 도시의 쌍을 순회하는 방법은 유일하다. (즉 도로의 그래프가 트리 형태이다)
도시가 공격당했을 때, 최대한 빠른 시간 내에 이 사실을 수도에 보고해야 한다. 각 도시에 살고 있는 전령들이 이 메시지를 전달한다. 각각의 전령에는 여정을 시작하기 위해 필요한 시간과 일정 속력(킬로미터 당 분 단위)이 있다.
도시에서 출발한 메시지는 수도까지 유일한 가장 짧은 경로를 통해서 전달된다. 처음에는 공격당한 도시의 전령이 메시지를 전달한다. 그 전령이 순회하는 다른 도시에서 전령은 두 가지 선택을 할 수 있다. 수도 방향의 다음 도시로 이동하거나, 그 도시의 전령에게 메시지를 남길 수 있다. 새로운 전령은 위와 같은 방식을 따른다. 종합해보면, 메시지는 수도까지 전달되는 동안 여러 전령을 거칠 수 있다.
이때, 각 도시에서 수도까지 메시지를 전하는데 걸리는 최소 시간을 구하여라.
첫째 줄엔, 몰다비아의 도시의 개수 N이 주어진다.
다음 줄부터 N-1개의 줄에 공백으로 구분된 세 개의 정수 U, V, D가 주어진다. 이는 도시 U와 도시 V 사이에 D 킬로미터의 도로가 있음을 의미한다.
그 아래에, 한 줄에 하나씩 N-1개의 정수 쌍이 주어진다. i번째 쌍인 Si, Vi는 (i+1)번째 도시의 전령을 표현하는 수이다. Si는 여정을 준비하는데 걸리는 시간, Vi는 1km를 가는데 걸리는 시간(분)이다. 수도에는 전령이 없다.
표준 출력에는 N-1개의 정수로 이루어진 하나의 줄을 출력해야 한다. i번째 수는 (i+1)번째 도시에서 수도로 메시지를 보내는데 필요한 최소 시간(분)을 나타낸다.
5 1 2 20 2 3 12 2 4 1 4 5 3 26 9 1 10 500 2 2 30
206 321 542 328
Olympiad > Central European Olympiad in Informatics > CEOI 2009 > Day 1 2번