시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 41 | 8 | 5 | 15.152% |
1부터 N까지 번호가 붙여진 N개의 마을과 이들 마을을 연결하는 도로망이 있다. 이 도로망에서는, 각 마을로부터 다른 모든 마을까지 가는 경로는 하나뿐이다. 각 마을에 사는 사람들의 수와 각 도로를 지나는데 걸리는 시간이 주어진다. 그리고 이들 마을 중 서로 다른 두 마을에만 병원이 있다.
마을 A에서 마을 B까지 가는데 걸리는 시간은 A에서 B까지의 경로 상에 있는 도로들의 통행시간의 합이다.
예를 들어, 다음과 같은 도로망을 고려해 보자.
그림 1
동그라미는 마을을 나타내고, 동그라미 안에 있는 수는 마을의 번호이고, 바깥에 있는 수는 마을에 있는 사람들의 수이다. 선분은 도로를 나타내고, 선분 상의 수는 도로의 통행시간을 나타낸다. 또한 병원이 세워져 있는 두 마을은 회색으로 칠해져 있다.
예산을 도로개선에 투입하여 도로의 통행시간을 줄일 수 있다. 이때 각 도로는 예산 C를 들이면 통행시간을 C 시간 만큼 줄일 수 있다. 이제 다음의 제약조건을 만족하면서 전체 예산 B를 도로개선에 투입한다.
제약조건:
L과 B의 값은 입력으로 주어진다.
이때, 위의 제약조건을 만족하면서 다음 두 질문의 답을 구하는 프로그램을 작성하시오.
그림 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이 된다.
어떻게 하더라도 위의 두 답보다 좋게 할 수 없다.
첫 번째 줄에 B(1 ≤ B ≤ 4,000,000)와 L(1 ≤ L ≤ 1,000)을 나타내는 두개의 양의 정수가 빈칸을 사이에 두고 주어진다. 두 번째 줄에 마을의 수 N (2 ≤ N ≤ 4,000)이 주어진다. 세 번째 줄에 마을 1부터 마을 N까지 각 마을에 사는 사람들의 수(1 이상 500 이하)가 빈칸을 사이에 두고 차례로 주어진다. 그 다음 줄부터 N-1개의 각 줄에 도로의 정보 즉, 도로의 양끝 마을 번호와 도로의 통행시간(1 이상 1,000 이하)을 나타내는 세 개의 양의 정수가 빈칸을 사이에 두고 차례로 주어진다. 마지막 줄에 병원이 있는 서로 다른 두 마을의 번호가 빈칸을 사이에 두고 주어진다.
반드시 질문 1의 답은 첫째 줄에, 질문 2의 답은 둘째 줄에 출력한다. 답이 232을 넘을 수 있음에 유의하라.
7 6 8 50 20 10 10 5 20 30 15 1 3 9 3 2 8 3 4 5 4 5 9 7 5 9 8 5 7 3 6 5 3 5
875 7
Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2010 > 중등부 5번
Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2010 > 고등부 4번