結果

問題 No.1 道のショートカット
コンテスト
ユーザー C++
提出日時 2024-02-20 17:34:38
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 46 ms / 5,000 ms
コード長 673 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 163 ms
コンパイル使用メモリ 84,824 KB
実行使用メモリ 69,440 KB
最終ジャッジ日時 2026-04-15 14:48:28
合計ジャッジ時間 2,932 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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