시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 7577 | 1903 | 1015 | 19.610% |
주언이는 경제학을 배워 행상인이 되었다. 두 도시를 오가며 장사를 하는데, 통행료의 합이 가장 적은 경로로 이동하려 한다. 도시들은 양방향 도로로 연결되어있으며, 도로마다 통행료가 존재한다.
그런데 정부는 세금 인상안을 발표하였다. 세금을 한 번에 올리면 문제가 발생할 수 있으므로 여러 단계에 걸쳐서 올린다고 한다. 세금이 A만큼 오르면 모든 도로의 통행료가 각각 A만큼 오르게 된다. 세금이 오르게 되면 주언이가 내야 하는 통행료가 변할 수 있다.
주언이를 도와 초기의 최소 통행료와 세금이 오를 때마다의 최소 통행료를 구하시오.
첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다.
두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D)가 주어진다. 각각 출발 도시와 도착 도시 번호를 의미한다. 도시 번호는 1부터 시작한다.
다음 M개의 줄에는 각각 도로 정보를 나타내는 세 정수 a, b (1 ≤ a < b ≤ N), w (1 ≤ w ≤ 1,000)가 주어진다. 도시 a와 도시 b가 통행료 w인 도로로 연결되어 있다는 것을 의미한다.
다음 총 K개의 줄에는 각각 정수 p (1 ≤ p ≤ 10)가 주어진다. 각각 첫 번째, 두 번째, …, K 번째에 인상되는 세금을 의미한다.
S에서 D로 이동할 수 없는 경우는 주어지지 않는다.
첫 번째 줄에 세금이 오르기 전의 최소 통행료를 출력한다.
두 번째 줄부터 K개의 줄에 각각 첫 번째, 두 번째, …, K 번째 세금이 올랐을 때의 최소 통행료를 출력한다.
3 3 2 1 3 1 3 5 1 2 1 2 3 2 1 2
3 5 8
세금이 오르기 전
첫 번째 세금 인상 후
두 번째 세금 인상 후
University > 서강대학교 > 2016 Sogang Programming Contest > Champion H번
University > 서강대학교 > 2016 Sogang Programming Contest > Master H번