1부터 N까지 번호가 붙여진 N개의 마을과 이들 마을을 연결하는 도로망이 있다. 이 도로망에서는, 각 마을로부터 다른 모든 마을까지 가는 경로는 하나뿐이다. 각 마을에 사는 사람들의 수와 각 도로를 지나는데 걸리는 시간이 주어진다. 그리고 이들 마을 중 서로 다른 두 마을에만 병원이 있다.

마을 A에서 마을 B까지 가는데 걸리는 시간은 A에서 B까지의 경로 상에 있는 도로들의 통행시간의 합이다. 예를 들어, 다음과 같은 도로망을 고려해 보자.

동그라미는 마을을 나타내고, 동그라미 안에 있는 수는 마을의 번호이고, 바깥에 있는 수는 마을에 있는 사람들의 수이다. 선분은 도로를 나타내고, 선분 상의 수는 도로의 통행시간을 나타낸다. 또한 병원이 세워져 있는 두 마을은 회색으로 칠해져 있다.

예산을 도로개선에 투입하여 도로의 통행시간을 줄일 수 있다. 이때 각 도로는 예산 C 를 들이면 통행시간을 C 시간 만큼 줄일 수 있다. 이제 다음의 제약조건을 만족하면서 전체 예산 B 를 도로개선에 투입한다.

제약조건: (1) 도로에 예산을 아무리 많이 사용하더라도 각 도로의 통행시간을 L 미만으로 할 수는 없다. (2) 도로개선에 사용하는 전체예산은 B 이하이어야 한다. * L과 B의 값은 입력으로 주어진다.

이 때, 위의 제약조건을 만족하면서 다음 두 질문의 답을 구하는 프로그램을 작성하시오.

질문 1: 각 사람이 가까운 병원까지 가는데 걸리는 시간의 합이 가장 작도록 할 때, 시간의 합의 최소값은 얼마인가?

질문 2: 각 사람이 가까운 병원까지 가는데 걸리는 시간 중 가장 긴 시간이 최소가 되도록 할 때, 그 최소 시간은 얼마인가?

그림 1의 도로망에서 전체예산 B = 7이고, L = 6일 경우, 질문 1의 해는 도로 (1,3)에 예산 3을 사용하여 도로 (1,3)의 통행시간을 6으로 만들고, 도로 (2,3)에 예산 1을 사용하여 통행시간을 7로 만들고, 예산 3을 도로 (5,7)에 사용하여 통행시간을 6으로 만들면 각 사람이 병원을 이용하는데 걸리는 시간의 합은 50*6 + 20*7 + 10*5 + 20*5 +30*6 + 15*7 = 875이다.

질문 2의 해는 도로 (1,3), (4,5), (5,7)에 각각 비용 2를 사용하고, 도로 (2,3)에 비용 1을 사용하면 각 사람이 가까운 병원까지 가는데 걸리는 가장 긴 시간은 7이 된다.

어떻게 하더라도 위의 두 답보다 좋게 할 수 없다.

#2265 upload 113 done 10 how_to_reg 4

병원 timer 1s memory - MB

#2265

병원 1s - MB