시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
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)$
윤이가 마법을 적절히 활용했을 때 회사까지 도착하는데 걸리는 최단 시간을 출력한다.
$K = 0$
추가적인 제약 조건이 없다.
2 1 2 1 2 1 5 0
5
3 2 1 3 3 1 5 3 2 5 0
5
3 2 2 3 3 1 1 1 2 5 2 1 4 5 4
5
이 예제는 서브태스크 1의 조건을 만족하지 않는다.