結果

問題 No.1 道のショートカット
ユーザー lam6er
提出日時 2025-03-20 21:01:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 67 ms / 5,000 ms
コード長 1,384 bytes
コンパイル時間 274 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 70,208 KB
最終ジャッジ日時 2025-03-20 21:01:48
合計ジャッジ時間 3,753 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    # Build adjacency list
    adj = [[] for _ in range(N+1)]  # cities are 1-based
    for i in range(V):
        s = S[i]
        t = T[i]
        y = Y[i]
        m = M[i]
        adj[s].append( (t, y, m) )
    INF = float('inf')
    dp = [ [INF] * (C+1) for _ in range(N+1) ]
    dp[1][0] = 0  # starting at city 1, cost 0, time 0
    for i in range(1, N+1):
        for cost in range(C+1):
            if dp[i][cost] == INF:
                continue
            # Process each edge from i
            for (t, y, m) in adj[i]:
                new_cost = cost + y
                if new_cost > C:
                    continue
                if dp[t][new_cost] > dp[i][cost] + m:
                    dp[t][new_cost] = dp[i][cost] + m
    # Find the minimal time for city N with cost <= C
    min_time = INF
    for c in range(C+1):
        if dp[N][c] < min_time:
            min_time = dp[N][c]
    print(min_time if min_time != INF else -1)
if __name__ == '__main__':
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0