結果

問題 No.1449 新プロランド
ユーザー lam6er
提出日時 2025-03-26 15:45:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 162 ms / 2,000 ms
コード長 1,825 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 78,380 KB
最終ジャッジ日時 2025-03-26 15:46:17
合計ジャッジ時間 2,614 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx +=1
    
    roads = [[] for _ in range(N+1)]
    for _ in range(M):
        a = int(data[idx])
        idx +=1
        b = int(data[idx])
        idx +=1
        c = int(data[idx])
        idx +=1
        roads[a].append( (b, c) )
        roads[b].append( (a, c) )
    
    T = list(map(int, data[idx:idx+N]))
    idx += N
    T = [0] + T  # 1-based
    
    INF = 1 << 60
    
    # dist[u][p] = minimal time to reach u with accumulated P=p
    dist = [dict() for _ in range(N+1)]
    initial_p = T[1]
    initial_time = initial_p
    dist[1][initial_p] = initial_time
    heap = []
    heapq.heappush(heap, (initial_time, 1, initial_p))
    
    answer = -1
    
    while heap:
        t, u, p = heapq.heappop(heap)
        if u == N:
            answer = t
            break
        # Check if current t is larger than recorded minimal
        if p not in dist[u] or t > dist[u][p]:
            continue
        # Explore all adjacent roads
        for v, c in roads[u]:
            move_time = c // p
            new_time = t + move_time
            if v == N:
                # Check if this new_time is better for N
                if (p not in dist[v]) or new_time < dist[v].get(p, INF):
                    dist[v][p] = new_time
                    heapq.heappush(heap, (new_time, v, p))
            else:
                new_p = p + T[v]
                new_time_v = new_time + T[v]
                if (new_p not in dist[v]) or new_time_v < dist[v].get(new_p, INF):
                    dist[v][new_p] = new_time_v
                    heapq.heappush(heap, (new_time_v, v, new_p))
    
    print(answer)

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