結果

問題 No.1 道のショートカット
ユーザー H3PO4
提出日時 2020-04-19 09:29:22
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 139 ms / 5,000 ms
コード長 592 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-07-20 16:47:08
合計ジャッジ時間 3,565 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #

N, C, V = (int(input()) for _ in range(3))
tmp = list(zip(*[tuple(map(int, input().split())) for _ in range(4)]))
W = [[] for _ in range(N + 1)]
for t in tmp:
    W[t[0]].append(t[1:])

table = [[float('inf')] * (C + 1) for _ in range(N + 1)]  # 1-indexed
table[1][0] = 0
for s in range(1, N + 1):
    for c in range(C):
        if table[s][c] == float('inf'):
            continue
        for t, y, m in W[s]:
            if c + y > C:
                continue
            table[t][c + y] = min(table[t][c + y], table[s][c] + m)

print(ans if (ans := min(table[N])) != float('inf') else -1)
0