結果

問題 No.1 道のショートカット
ユーザー stnkien
提出日時 2020-06-12 00:39:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 807 bytes
コンパイル時間 236 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 76,664 KB
最終ジャッジ日時 2024-07-08 05:28:30
合計ジャッジ時間 10,821 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
C = int(input())
V = int(input())
*S, = map(int, input().split())
*T, = map(int, input().split())
*Y, = map(int, input().split())
*M, = map(int, input().split())

G = [[] for _ in [0]*(N+1)]
for s, *t in zip(S, T, Y, M):
    G[s].append(t)

INF = 10**10
D = [[INF]*(C+1) for _ in [0]*(N+1)]
D[1][C] = 0
used = set((1, C))

while True:
    dmin = INF
    z = -1

    for v in range(1, N+1):
        for c in range(C+1):
            if (v, c) not in used and D[v][c] < dmin:
                dmin = D[v][c]
                z = v, c
    if z == -1:
        break

    used.add(z)
    v, c = z
    for u, y, m in G[v]:
        if c-y < 0:
            continue
        if D[v][c]+m < D[u][c-y]:
            D[u][c-y] = D[v][c]+m

ans = min(D[N])
if ans == INF:
    print(-1)
else:
    print(ans)
0