結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2019-03-23 13:24:28 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 729 ms / 5,000 ms |
コード長 | 804 bytes |
コンパイル時間 | 87 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 44,504 KB |
最終ジャッジ日時 | 2024-07-20 16:39:13 |
合計ジャッジ時間 | 27,786 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#!/usr/bin/env python3 # -*- coding: utf-8-*- import numpy as np if __name__ == '__main__': INF = 10000000 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(" "))) vl = [ [] for i in range(n)] for i in range(v): vl[s[i]-1].append((t[i]-1, y[i], m[i])) t = np.full((n, c+1), INF) t[0,0] = 0 for i in range(n): for j in range(c+1): if t[i, j] == INF: continue for tt, yy, mm in vl[i]: if j+yy <= c: t[tt, j+yy] = min(t[i, j] + mm, t[tt, j+yy]) a = min(t[n-1, :]) if a == INF: a = -1 print(a)