結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2015-02-19 03:09:38 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 184 ms / 5,000 ms |
コード長 | 643 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 6,912 KB |
最終ジャッジ日時 | 2024-07-20 16:09:33 |
合計ジャッジ時間 | 3,142 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
N = input() C = input() M = input() S = map(int, raw_input().split()) T = map(int, raw_input().split()) D = map(int, raw_input().split()) M = map(int, raw_input().split()) E = [[] for _ in xrange(N)] for s, t, d, m in zip(S, T, D, M): E[s - 1].append((t - 1, d, m)) dist = [[float("inf")] * (C + 1) for _ in xrange(N)] dist[0][0] = 0 for v in xrange(N): for c in xrange(C + 1): for to, cost, time in E[v]: next_cost = c + cost if next_cost <= C: dist[to][next_cost] = min(dist[to][next_cost], dist[v][c] + time) ans = min(dist[N - 1]) print ans if ans != float("inf") else -1