Yukicoder No. 1 道のショートカット

Yukicoder No. 1 길 바로 가기

문제 링크

문제

$N$개의 마을이 있습니다. 각각에는 $1$부터 $N$까지의 번호가 붙어있습니다.
각각의 도시는 직접 길로 연결되어 있을 수도, 아닐 수도 있습니다.
각 길은 마을 $S_i$부터 마을 $T_i$까지 가는 데에 비용 $Y_i$엔이 들고, $M_i$ 단위시간이 듭니다.

당신은 마을 $1$에 있습니다.
$N$번 마을에 가고 싶습니다.
도로를 몇 개 사용하든 상관없지만, 당신은 $C$엔을 가지고 있습니다.

(즉, 사용한 비용 $Y_i$의 합이 $C$를 넘어서는 안 됩니다.)

그중 가장 빠른 경로를 사용할 때, 드는 총 시간을 출력해 주세요.
이 제약 안에서 도착할 수 있는 방법이 없는 경우 $-1$을 출력해주세요.

입력

$1$번째 줄에는, 마을의 수를 나타내는 정수 $N \ ( 2 \le N \le 50 )$이 주어집니다.
$2$번째 줄에는, 가지고 있는 돈을 나타내는 정수 $C \ ( 1 \le C \le 300 )$가 주어집니다.
$3$번째 줄에는, 길의 수를 나타내는 정수 $V \ ( 1 \le V \le 1500 )$가 주어집니다.
$4$번째 줄에는, $S_i \ ( 1 \le S_i \le N )$ $V$개가 공백으로 구분되어 주어집니다.
$5$번째 줄에는, $T_i \ ( S_i < T_i \le N )$ $V$개가 공백으로 구분되어 주어집니다.
$6$번째 줄에는, $Y_i \ ( 1 \le Y_i \le C )$ $V$개가 공백으로 구분되어 주어집니다.
$7$번째 줄에는, $M_i \ ( 1 \le M_i \le 1000 )$ $V$개가 공백으로 구분되어 주어집니다.

$S_i$, $T_i$, $Y_i$, $M_i$는 각각 마을 $S_i$ $\rightarrow$ 마을 $T_i$ (유향그래프) 이동에 $Y_i$ 비용이 들며, $M_i$ 단위시간이 걸린다는 의미입니다.

제약조건에 의해, $S_i < T_i$ 이므로 루프나 사이클이 존재하지 않고, 고려하지 않아도 됩니다.

길의 연결에 따라 마을 $N$으로 가는 방법이 없을 수도 있습니다.

$S_i \rightarrow T_i$ 경로가 여럿 있을 수도 있습니다.

출력

마을 $1$부터 마을 $N$까지 가장 일찍 도착했을 때, 드는 총 시간을 출력해주세요.
이 제약 안에서 불가능한 경우, -1을 출력해주세요.
마지막에 개행문자를 넣어주세요.

풀이

기본적인 최단 거리 알고리즘을 응용해서 풀 수 있는 문제입니다.

그냥 최단 거리 알고리즘을 사용할 때의 문제는, 경로의 비용을 관리할 방법이 없다는 것입니다. 가령이면, Dijkstra 알고리즘에서, 비용이 적게 드는 것을 큐에 넣는 쪽이 되면, 비용과 시간 중에 어느 쪽이 이득이 되는 것으로 골라야 할지 모릅니다. 결론적으로, 현재 상태를 (비용, 도시 번호)로 저장해서, 모든 상태를 저장하게 됩니다.

가능한 상태의 개수는 $O(NC)$개이고, 가능한 상태 전이의 수는 $O(CV)$개 이므로, 총 시간 복잡도는 $O(CV \log(NC))$ 정도가 됩니다.

그래프에 사이클이 없다는 점을 이용해서, DAG 위에서 DP를 사용해도 문제를 풀 수 있습니다. Dijkstra 알고리즘 대신 사용하면, 시간 복잡도의 $\log(NC)$가 줄어서, 시간 복잡도가 $O(CV)$가 됩니다.

 

코드: https://yukicoder.me/submissions/732190