結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2015-02-16 00:37:46 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 113 ms / 5,000 ms |
コード長 | 492 bytes |
コンパイル時間 | 101 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-07-20 16:09:12 |
合計ジャッジ時間 | 2,806 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
inf = 10**9 N,C,V = [int(raw_input()) for i in range(3)] S,T,Y,M = [map(int,raw_input().split()) for i in range(4)] G = [[[] for i in xrange(N)] for j in xrange(N)] for s,t,y,m in zip(S,T,Y,M): G[s-1][t-1].append([y,m]) dp = [[inf]*(C+1) for i in xrange(N)] dp[0][C] = 0 for i in xrange(N): for j in xrange(i+1,N): for y,m in G[i][j]: for c in xrange(y,C+1): dp[j][c-y] = min(dp[j][c-y], dp[i][c]+m) ans = min(dp[N-1]) print ans if ans < inf else -1