cho.sh

택시 여행

아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

IOI 나라는 NN개의 도시와 도시들을 잇는 N−1N - 1개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 도시를 도로만을 사용하여 오갈 수 있다. 즉, IOI 나라의 도로망은 트리 구조를 이룬다.

도시에는 각각 00 이상 N−1N - 1 이하의 서로 다른 번호가 붙어 있으며, 00번 도시가 IOI 나라의 수도이다. 또 모든 0≤i≤N−20 ≤ i ≤ N - 2에 대해서 ii번 도로는 U\[i]U\[i]번 도시와 V\[i]V\[i]번 도시를 연결하며 도로의 길이는 W\[i]W\[i] km 이다.

IOI 나라에서는 도시별로 택시의 운임이 다르다. 구체적으로, 모든 0≤i≤N−10 ≤ i ≤ N - 1에 대해 ii번 도시에서 출발하는 택시는 기본 요금 A\[i]A\[i]원과 거리 당 요금 B\[i]B\[i]원을 가진다. 이는 ii번 도시에서 택시를 타고 출발하여 dd km 만큼 이동할 경우 A\[i]+d×B\[i]A\[i] + d \times B\[i]원을 내야 함을 뜻한다.

서현이는 현재 수도인 00번 도시에 살고 있다. 서현이는 다른 도시들로 택시를 타고 여행을 떠나려고 한다. 서현이가 어떤 도시에 도착했을 때, 서현이는 타던 택시를 계속 타거나 그 도시에서 출발하는 택시로 갈아탈 수 있다. 물론 택시를 갈아타면 기본 요금을 내야 하며 거리 당 요금도 변할 수 있다. 00번 도시에서 출발하여 다른 모든 도시들로 가는 데 필요한 최소 비용을 각각 계산하여라.

제한

  • 2≤N≤100,0002 ≤ N ≤ 100\\,000
  • 모든 ii에 대해 0≤A\[i]≤10120 ≤ A\[i] ≤ 10^{12} (0≤i≤N−10 ≤ i ≤ N - 1)
  • 모든 ii에 대해 0≤B\[i]≤1,000,0000 ≤ B\[i] ≤ 1\\,000\\,000 (0≤i≤N−10 ≤ i ≤ N - 1)
  • 모든 ii에 대해 0≤U\[i],V\[i]≤N−10 ≤ U\[i], V\[i] ≤ N - 1; U\[i]≠V\[i]U\[i] \ne V\[i] (0≤i≤N−20 ≤ i ≤ N - 2)
  • 모든 ii에 대해 1≤W\[i]≤1,000,0001 ≤ W\[i] ≤ 1\\,000\\,000 (0≤i≤N−20 ≤ i ≤ N - 2)