結果

問題 No.1 道のショートカット
ユーザー lam6er
提出日時 2025-03-20 18:40:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 60 ms / 5,000 ms
コード長 1,195 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 67,684 KB
最終ジャッジ日時 2025-03-20 18:41:25
合計ジャッジ時間 3,658 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0

    N = int(input[ptr])
    ptr +=1
    C = int(input[ptr])
    ptr +=1
    V = int(input[ptr])
    ptr +=1

    S = list(map(int, input[ptr:ptr+V]))
    ptr +=V
    T = list(map(int, input[ptr:ptr+V]))
    ptr +=V
    Y = list(map(int, input[ptr:ptr+V]))
    ptr +=V
    M = list(map(int, input[ptr:ptr+V]))
    ptr +=V

    adj = [[] for _ in range(N+1)]
    for i in range(V):
        s = S[i]
        t = T[i]
        y = Y[i]
        m = M[i]
        adj[s].append( (t, y, m) )

    INF = 1 << 60
    dp = [ [INF] * (C + 1) for _ in range(N + 1) ]
    dp[1][0] = 0

    for i in range(1, N):  # Process towns up to N-1
        for c in range(C + 1):
            if dp[i][c] == INF:
                continue
            for (j, y, m) in adj[i]:
                new_cost = c + y
                if new_cost > C:
                    continue
                if dp[j][new_cost] > dp[i][c] + m:
                    dp[j][new_cost] = dp[i][c] + m

    res = INF
    for c in range(C + 1):
        if dp[N][c] < res:
            res = dp[N][c]

    print(res if res != INF else -1)

if __name__ == "__main__":
    main()
0