結果

問題 No.1 道のショートカット
ユーザー sotanishy
提出日時 2021-03-16 19:37:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 141 ms / 5,000 ms
コード長 815 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 77,648 KB
最終ジャッジ日時 2024-11-08 09:23:04
合計ジャッジ時間 4,801 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N = int(input())
C = int(input())
V = int(input())
S = list(map(lambda x: int(x) - 1, input().split()))
T = list(map(lambda x: int(x) - 1, input().split()))
Y = list(map(int, input().split()))
M = list(map(int, input().split()))

G = [[] for _ in range(N)]
for s, t, y, m in zip(S, T, Y, M):
    G[s].append((t, y, m))

INF = 10**18
dist = [[INF] * (C + 1) for _ in range(N)]
dist[0][0] = 0
pq = [(0, 0, 0)]
while pq:
    d, s, c = heappop(pq)
    if dist[s][c] < d:
        continue
    for t, y, m in G[s]:
        if c + y > C:
            continue
        nd = d + m
        nc = c + y
        if nd < dist[t][nc]:
            dist[t][nc] = nd
            heappush(pq, (nd, t, nc))
ans = min(dist[-1])
print(ans if ans < INF else -1)
0