【yukicoder】No.1 道のショートカット
個の町々で目的の町を目指して、時間内にもっとも安い値段で辿り着く場合を求める問題です。
問題
問題はこちら
解法
動的計画法で解きます。
ちなみに動的計画法の参考記事では下記の記事がとてもわかりやすいです。
典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ - Qiita
という行列を考えます。
問題のサンプル1では下記のような行列になります。(ここではコストの桁を1つ減らしています)
# 入力 3 10 3 1 2 1 2 3 3 1 9 1 10 10 50
$$ A= \begin{pmatrix} 0 & N & N & N & N & N & N & N & N & N & N \\ N & 10 & N & N & N & N & N & N & N & N & N \\ N & 50 & N & N & N & N & N & N & N & N & 20 \\ \end{pmatrix} $$
コストは0を含むので列は 列になるので注意です。
3行でもっともコストが低いのは20となり、これが答えです。
ただし行列の各値を計算する場合は、道順のスタートが 1,2,3, ... と若い順に見ていくように注意する必要があります。
Python3
コード
n=int(input()) c=int(input()) v=int(input()) S=list(map(int,input().split())) T=list(map(int,input().split())) Y=list(map(int,input().split())) M=list(map(int,input().split())) z=zip(S,T,Y,M) d=[[None]*(c+1) for i in range(n)] d[0][0] = 0 for s,t,y,m in sorted(z,key=lambda x:(x[0],x[1])): for j in range(c+1): a=d[s-1][j] if a is not None: q=y+j if c<q: break p=t-1 x=a+m if d[p][q] is None or x<d[p][q]: d[p][q]=x o=None for x in d[n-1]: if x is not None: if o is None or x<o: o=x print(-1 if o is None else o)
d=[[None]*(c+1) for i in range(n)]
で 行 列の行列を各値None
で初期化しています。
for s,t,y,m in sorted(z,key=lambda x:(x[0],x[1])):
で 1 → 2
, 1 → 3
, ... のように若い番号からの道順から計算するようにしています。d[0][0] = 0
はスタート地点1の町は0時間かけて金額0円で行けることを意味します。
道順をループし到着する町 s
の町、すなわち s-1
行目の列を見ていき、行列値 a
の値が None
でなければ、次の町 t
へ行くまでにかかる時間を代入します。
このとき、金額の値(列数)が超えないようにするのと、経過時間が最小値になるように判定しておく必要があります。