홍윤이와 여행하기 서브태스크 1초 512MB
문제
홍윤이는 여행과 커피를 좋아한다.
KOI국에는 1번부터 N번까지의 번호가 붙은 N개의 도시가 있고, N-1개의 양방향 도로들로 연결되어 있으며 임의의 도시에서 다른 어떤 도시로도 도로들만을 사용하여 이동이 가능하다. KOI국의 모든 도시에서 커피를 마셔보기로 결심한 홍윤이는 1번 도시에서 시작하여 2번 도시로 이동한다. 2번 도시로 이동하는 동안 다른 도시들을 지날 수도 있지만 지나가는 도시들에서는 커피를 마시지 않는다. 이와 같이 2번 도시에 도착한 이후에는 3번 도시로 이동하고, 이를 반복하여 N번 도시까지 이동하여 커피를 마신다.
도로 하나를 지나기 위해서는 티켓이 필요하다. i번째 도로를 건너기 위해서는 Ci1원을 내고 일회용 티켓을 구매할 수도 있고, Ci2원을 내고 다회용 티켓을 구매할 수도 있다. 각 도로에 대하여 건널 때마다 일회용 티켓을 구매할 수도 있고, 다회용 티켓을 하나만 구매하여 사용할 수도 있다.
홍윤이가 여행을 성공적으로 마치기 위해 구매하여야 하는 티켓의 금액의 합의 최솟값을 구하여라.
입력
첫 번째 줄에 정수 N (2 ≤ N ≤ 200 000) 이 주어진다.
이후 N-1 개의 줄에 Ai, Bi, Ci1, Ci2 (1 ≤ Ai, Bi ≤ N, 1 ≤ Ci1 ≤ Ci2 ≤ 100 000) 이 주어지고, 도시 Ai, Bi가 연결되어 있으며 일회용 티켓의 금액은 Ci1, 다회용 티켓의 금액은 Ci2임을 의미한다.
출력
첫 번째 줄에 여행의 최소 비용을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 15점 | 2 ≤ N ≤ 2,000 |
| #2 | 20점 | 모든 도시는 최대 2개의 도시와 연결되어 있다. |
| #3 | 65점 | 추가 제약조건 없음. |
예제 #1
4
1 2 3 5
1 3 2 4
2 4 1 3
10
예제 #2
4
1 4 5 5
3 4 4 7
2 4 2 6
16
예제 #3
5
1 2 2 3
1 3 2 3
1 4 2 3
1 5 2 3
11
로그인해야 코드를 작성할 수 있어요.