20313번 - 출퇴근 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 338 | 96 | 65 | 25.896% |
문제
윤이는 유니마을에 거주하는 주민이다. 유니마을은 $1$번부터 $N$번까지 번호가 붙은 $N$개의 건물로 이루어져 있다. 윤이는 그 중 $A$번 건물에 거주하고 있으며, $B$번 건물에 있는 회사로 매일 출퇴근한다.
유니마을은 다음과 같은 구조를 가지고 있다. $N$개의 건물을 잇는 $M$개의 양방향 도로 $R_i$가 있고, 적절한 순서로 도로를 이용하면 임의의 두 건물 사이에 이동이 가능하다. 도로 $R_i$는 서로 다른 $U_i$번 건물과 $V_i$번 건물을 이으며, $R_i$를 거쳐 이동하는 데에는 $T_i$ 만큼의 시간이 소요된다. 한 쌍의 건물을 직접 잇는 도로는 최대 하나이다.
그러던 어느 날, 윤이는 자신이 마법을 쓰면 교통 상황을 바꾸어서 각 도로들을 이동하는데 소모되는 시간을 바꿀 수 있음을 알게 되었다. 윤이는 최대 $K$번 마법을 쓸 수 있는데, 마법을 $k$번 사용하고 나면 모든 $i$에 대해 도로 $R_i$를 이동하는 데 걸리는 시간이 $T_{i, k}$가 된다고 한다. 윤이는 건물에 있을 때만 마법을 사용할 수 있고, 도로를 지나가는 중에 마법을 사용할 수는 없다.
윤이는 마법을 적절히 활용해서 최단 시간으로 회사까지 도착하고자 한다. 윤이를 도와 회사까지 도착하는 데 필요한 최단 시간을 구하시오.
입력
입력의 첫 줄에 $N$과 $M$, 그리고 $A$와 $B$가 주어진다.
다음 $M$개의 줄에 걸쳐 $U_i, V_i, T_i$의 값이 공백을 사이에 두고 주어진다. $(1 \le i \le M)$
다음 줄에 $K$가 주어진다.
다음 $K$개 줄의 $k$번째 줄에는 $T_{1, k}, T_{2, k}, \cdots, T_{M, k}$가 사이에 공백을 두고 주어진다. $(1 \le k \le K)$
출력
윤이가 마법을 적절히 활용했을 때 회사까지 도착하는데 걸리는 최단 시간을 출력한다.
제한
- $2 \le N \le 1,000$
- $N-1 \le M \le 2,000$
- $M \le N(N-1)/2$
- $1\le A, B, U_i, V_i\le N, A\ne B, U_i \ne V_i$
- $0 \le K \le 100$
- $0 \le T_i, T_{i,k} < 10^9$
서브태스크 1 (35점)
$K = 0$
서브태스크 2 (115점)
추가적인 제약 조건이 없다.
예제 입력 1
2 1 2 1 2 1 5 0
예제 출력 1
5
예제 입력 2
3 2 1 3 3 1 5 3 2 5 0
예제 출력 2
5
예제 입력 3
3 2 2 3 3 1 1 1 2 5 2 1 4 5 4
예제 출력 3
5
이 예제는 서브태스크 1의 조건을 만족하지 않는다.
출처
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2022 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호