시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 2627 | 781 | 515 | 31.556% |
아래와 같이 M행 N열 격자 그리드로 설계된 운전 면허 시험장에서 운전 면허 시험을 치르려 한다.
시험의 규칙은 세 가지이다.
규칙 2를 만족하기 위해, 응시자는 도로의 상태에 따라 알맞은 방법으로 차를 몰아야 한다. 따라서, 각 도로의 상태에 따라 소모되는 연료량이 다르다. 이에 따라 응시자는 G 이하의 연료만을 사용하여 t에 도착하는 경로를 찾아야 한다.
위에 예시로 주어진 4*6 그리드에서 각 도로에 쓰여진 정수가 그 도로를 시간 L동안 주행하는 데에 드는 연료량이다. 방향을 바꿀 때는 연료가 사용되지 않는다.
위의 그림은 G=19이며 L=10일 때 가능한 두 가지 경로를 표시한 것이다.
왼쪽의 경로는 17의 연료를 사용하여 83의 시간만에 아래에 도달하는 경로이다. 이 경로에는 8번의 직선 주행과 3번의 방향 변경이 있었다. 오른쪽의 경로는 연료를 덜 쓰는 경로이지만(16), 주행 시간의 합이 85로 더 오래 걸린다. 사실 위의 경로 외에도 19 이하의 연료 사용으로 83의 시간으로 도달할 수 있는 경로가 몇 가지 더 있다. 하지만, 19 이하의 연료를 사용하여 83보다 더 빠른 시간 내에 t에 도착하는 방법은 존재하지 않는다.
이제 주행 시험이 시작된다. 그리드의 상태와 G, L이 주어질 때, 가장 빠르게 목적지 t에 도달하는 시간은 얼마일까?
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 네 개의 정수 M, N, L, G로 이루어져 있으며 M은 그리드의 행 수, N은 그리드의 열 수이다. L은 문제에서 설명한 한 격자를 직선 주행하는 데 걸리는 시간이며 G는 연료량이다. (2 ≤ M, N ≤ 100), (1 ≤ L ≤ 10), (1 ≤ G ≤ 1,000,000). 이어서 M줄에 걸쳐 N-1개의 정수가 주어진다. 각 정수는 그리드에서 대응되는 가로 경로를 주행할 때 드는 연료량이다. 그 이후 M-1줄에 걸쳐 N개의 정수가 주어진다. 각 정수는 그리드에서 대응되는 세로 경로를 주행할 때 드는 연료량이다.
모든 단위 경로에서 소모되는 연료량은 1 이상 1000 이하의 값을 갖는다.
만일 G 이하의 연료량으로 s에서 t까지 가는 것이 가능하다면 가능한 한 빨리 도착했을 때 걸리는 시간을, 불가능하다면 -1을 출력한다.
3 4 6 10 19 4 3 6 7 9 3 1 2 7 5 2 2 6 1 9 5 3 4 3 2 1 5 4 4 4 2 6 1 1 3 1 7 2 2 3 2 3 5 3 4 5 10 4 5 6 2 3 1 5 7 8 1 8 6 7 4 6 9 1 3 3 10 9 2 2 2 2 2 2 3 3 3 3 3 3
83 27 -1
ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2014 B번