結果

問題 No.1 道のショートカット
ユーザー yuppe19 😺
提出日時 2015-10-26 17:57:36
言語 Python2
(2.7.18)
結果
AC  
実行時間 188 ms / 5,000 ms
コード長 714 bytes
コンパイル時間 775 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 6,912 KB
最終ジャッジ日時 2024-07-20 16:17:41
合計ジャッジ時間 3,598 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/python
inf = float('inf')
N = int(raw_input())
C = int(raw_input())
V = int(raw_input())
S = map(lambda x: int(x)-1, raw_input().split())
T = map(lambda x: int(x)-1, raw_input().split())
Y = map(int, raw_input().split())
M = map(int, raw_input().split())
route = [[] for _ in xrange(N)]
for i in xrange(V):
    route[S[i]].append((T[i], Y[i], M[i]))
dp = [[inf for _ in xrange(C+1)] for _ in xrange(N)]
dp[0][0] = 0
for v in xrange(N):
    for c in xrange(C+1):
        for to, cost, time in route[v]:
            ncost = cost + c
            if ncost > C:
                continue
            dp[to][ncost] = min(dp[to][ncost], dp[v][c] + time)
res = min(dp[N-1])
if res == inf:
    res = -1
print res
0