結果

問題 No.1 道のショートカット
コンテスト
ユーザー C++
提出日時 2024-02-20 17:34:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 61 ms / 5,000 ms
コード長 673 bytes
コンパイル時間 135 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 70,200 KB
最終ジャッジ日時 2024-09-29 03:46:49
合計ジャッジ時間 2,952 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
INF = 10 ** 10
def inp() -> str : return input()
def i() -> int : return int(input())
def lis() -> list[int] : return list(map(int, input().split()))

n = i()
c = i()
v = i()
ss = lis()
tt = lis()
ys = lis()
ms = lis()

graph = [[] for _ in range(n)]
for s, t, y, m in zip(ss, tt, ys, ms):
  graph[s - 1].append([t - 1, y, m])

cost = [[INF] * (c + 1) for _ in range(n)]
cost[0][c] = 0

que = deque([(c, 0)])
while que:
  c, s = que.popleft()
  for t, y, m in graph[s]:
    if y <= c and cost[t][c - y] > cost[s][c] + m:
      cost[t][c - y] = cost[s][c] + m
      que.append((c - y, t))
ans = min(cost[n - 1])
print(-1 if ans == INF else ans)
0