結果

問題 No.1 道のショートカット
ユーザー rlangevin
提出日時 2023-11-17 12:30:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 726 ms / 5,000 ms
コード長 1,159 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 84,352 KB
最終ジャッジ日時 2024-09-26 05:22:02
合計ジャッジ時間 6,296 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
inf = 10 ** 18

def dijkstra2(N):
    ind = 0
    D = [inf] * (N)
    seen = [False] * (N)
    D[0] = 0
    while True:
        minv = inf
        ind = N + 1
        for i in range(N):
            if seen[i]:
                continue
            if D[i] < minv:
                ind = i
                minv = D[i]
        if ind == N + 1:
            break
        if ind // (C + 1) == N - 1:
            return D
        seen[ind] = True
        for u, d in G[ind]:
            if seen[u]:
                continue
            D[u] = min(D[u], D[ind] + d)
    return D

N = int(input())
C = int(input())
V = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
Y = list(map(int, input().split()))
M = list(map(int, input().split()))
N2 = N * (C + 1)
G = [[] for i in range(N2)]
for i in range(V):
    s, t = S[i] - 1, T[i] - 1
    for c in range(C + 1):
        if c + Y[i] <= C:
            G[s * (C + 1) + c].append((t * (C + 1) + c + Y[i], M[i]))

D = dijkstra2(N2)
ans = inf
for i in range(C + 1):
    ans = min(ans, D[(N - 1) * (C + 1) + i])

print(ans) if ans != inf else print(-1)
0