| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 29 | 22 | 21 | 77.778% |
본 문제와 Large 문제는 입력의 제한과 출력 조건이 다르다. ”입력”과 ”출력” 문단을 참조하라.
오래된 놀이공원의 주인인 인서는 놀이공원을 새롭게 단장하기 위해 자신의 가장 유능한 직원인 정우에게 리모델링을 지시하였다. 리모델링의 책임자가 된 정우는 우선 놀이공원의 상태를 아래와 같이 파악하였다.
정우는 위와 같은 놀이공원의 상태를 바탕으로 고객에 대해 아래와 같은 가설을 설립하였다.
정우는 고객들의 편의를 위하여 최단소요시간을 더 줄이고자 아래의 기준을 설립하였다.
정우를 위해 최단소요시간의 최대 감소량을 구하는 프로그램을 작성하도록 하자.
첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. $(4 \le N \le 100$; $1 \le M \le \frac{N(N-1)}{2})$
그다음 줄부터 $N$개의 줄에 걸쳐 놀이기구 정보가 주어진다. 그중 $i$번째 줄은 정수 $T_i$, $P_i$가 공백으로 구분되어 주어진다. $(1 \le i \le N$; $1 \le T_i, P_i \le 100)$
그다음 줄부터 $M$개의 줄에 걸쳐 공원포탈 정보가 주어진다. 그중 $j$번째 줄은 정수 $u_j$, $v_j$, $S_j$가 공백으로 구분되어 주어진다. $(1 \le j \le M$; $1 \le u_j, v_j \le N$; $1 \le S_j \le 100)$
첫 번째 줄에 최단소요시간의 최대 감소량을 출력한다.
만약 다음 조건을 만족한다면 첫 번째 줄에 -1을 대신 출력한다.
4 5 1 5 2 6 3 7 4 8 1 2 20 1 3 2 2 4 11 3 2 3 3 4 10
9
4 5 1 5 2 6 3 7 4 8 1 2 20 1 3 2 2 3 3 3 3 10 4 1 5
-1
University > 중앙대학교 > 중앙대학교 프로그래밍 경진대회 (CPC) > 2019 중앙대학교 프로그래밍 경진대회 (CPC) E번
University > 중앙대학교 > 중앙대학교 프로그래밍 경진대회 (CPC) > 2026 중앙대학교 프로그래밍 경진대회 (CPC) E1번