結果

問題 No.1 道のショートカット
ユーザー rpy3cpp
提出日時 2015-03-25 22:41:28
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,198 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-07-08 03:50:01
合計ジャッジ時間 2,767 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 34 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def read_data():
    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()))
    return N, C, V, S, T, Y, M

def solve(N, C, V, S, T, Y, M):
    Es = init_Es(N, S, T, Y, M)
    hq = []
    pos = 1
    time = 0
    cost = 0
    status = (time, cost, pos)
    heapq.heappush(hq, status)
    t = [float('inf') for i in range(N + 1)]
    while hq:
        time, cost, pos = heapq.heappop(hq)
        if pos == N:
            return time
        for new_pos, dif_cost, dif_time in Es[pos]:
            new_cost = cost + dif_cost
            new_time = time + dif_time
            if t[new_pos] > new_time and new_cost <= C:
                t[new_pos] = new_time
                status = (new_time, new_cost, new_pos)
                heapq.heappush(hq, status)
    return -1

def init_Es(N, S, T, Y, M):
    Es = [[] for i in range(N+1)]
    for s, t, y, m in zip(S, T, Y, M):
        Es[s].append((t, y, m))
    return Es


if __name__ == '__main__':
    N, C, V, S, T, Y, M = read_data()
    print(solve(N, C, V, S, T, Y, M))
0