dlaud5379   8달 전

(기존에 번역이 있었다고 해서 참고용으로 작성합니다. 원래 번역이 어떤 내용이었는지 모르는 채로 재번역했기 때문에 내용이 기존과 많이 달라져있을 수 있습니다.)

문제

솔브드 왕국의 도로망은 1번부터 N번까지 N개의 도시와 도시를 서로 연결하는 N-1개의 도로로 이루어져 있다. 도로망은 서로 다른 두 도시의 쌍을 어떻게 고르더라도 두 도시를 잇는 경로가 유일하게 존재하도록 구성되어 있다.

최근에는 도로망이 잘 정비되지 않아 도로의 상태가 양호하지 못하다. 각 도로마다 현 상태를 유지했을 때 걸리는 시간 A와 그 도로를 완전히 정비했을 때 걸리는 최소 시간 B가 초 단위의 정수로 주어진다.

솔브드 왕국에서는 세금을 투입해 도로를 정비하려고 한다. 도로 정비의 효과는 그 도로에 투입한 세금에 비례한다. 구체적으로 어떤 도로에 별조각 1개를 투입할 때마다 그 도로를 통과하는 데 걸리는 시간이 1초씩 줄어든다. 별조각은 정수 개수로만 사용할 수 있으며, 도로를 통과하는 데 걸리는 시간을 위에서 언급한 B 미만으로 줄일 수는 없다.

솔브드 도로공사에서는 정비 이후 1번 도시에서 가장 먼 도시까지 이동하는 시간이 최소가 되도록 하는 정비안을 구상했다. 솔브드 왕국에서 편성한 예산이 주어졌을 때, 예산을 적절히 집행했을 때 1번 도시에서 가장 먼 도시까지 이동하는 최소 시간을 구하는 프로그램을 작성하여라.

입력

첫째 줄에 도시의 수 N과 예산으로 편성된 별조각 수 K가 주어진다. (2 ≤ N ≤ 100 000, 0 ≤ K ≤ 1 000 000)

둘째 줄부터 N-1줄에 걸쳐 도로의 정보가 주어진다. 각 도로는 X, Y, A, B의 네 정수로 주어지며, 이는 도로가 X번 도시와 Y번 도시를 연결하고 문제에서 설명한 현재 이동 시간과 최소 이동 시간이 각각 A와 B라는 의미이다. (0 ≤ B ≤ A ≤ 10 000)

출력

문제의 정답을 한 줄로 출력한다.

댓글을 작성하려면 로그인해야 합니다.