No.1

$i$ 番目の町にコスト $c$ で到達したときの到達時間を $T(i, c)$ として, $i$ 番目の町から $j$ 番目の町にたどり着くためのコストと時間を $C_{ij}, M_{ij}$ とすると,

$$T(j, c + C_{ij}) = \min(T(i, c) + M_{ij}) \qquad (i \in j \text{につながっている町})$$

となる. これを DP で計算し, $T(N, \ast)$ の最小値を求める.