結果

問題 No.1449 新プロランド
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:42:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,197 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 79,292 KB
最終ジャッジ日時 2025-03-31 17:43:20
合計ジャッジ時間 2,735 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    
    edges = [[] for _ in range(N+1)]
    for _ in range(M):
        a = int(input[idx])
        idx += 1
        b = int(input[idx])
        idx += 1
        c = int(input[idx])
        idx += 1
        edges[a].append((b, c))
        edges[b].append((a, c))
    
    T = list(map(int, input[idx:idx+N]))
    idx += N
    t_list = [0] * (N + 1)  # t_list[i] is T_i for town i
    for i in range(N):
        t_list[i + 1] = T[i]
    
    # Using a priority queue: (time, town, current_p)
    heap = []
    heapq.heappush(heap, (0, 1, 0))
    
    # dist is a dictionary of dictionaries. dist[town][p] = min_time
    dist = [dict() for _ in range(N + 1)]
    dist[1][0] = 0
    
    while heap:
        current_time, u, p_current = heapq.heappop(heap)
        
        if u == N:
            print(current_time)
            return
        
        # Check if the current recorded time is the smallest
        if p_current not in dist[u] or dist[u][p_current] < current_time:
            continue
        
        # Calculate new p after eating in town u
        T_u = t_list[u]
        p_new = p_current + T_u
        
        for v, c in edges[u]:
            if v == u:
                continue  # Should not happen as per the problem's input
            # Calculate move time
            move_time = c // p_new
            total_time = current_time + T_u + move_time
            
            # Check if we can update the state for town v with p_new
            if v == N:
                # Update the answer immediately
                print(total_time)
                return
            else:
                if p_new in dist[v]:
                    if dist[v][p_new] <= total_time:
                        continue
                # Update if this is a better path
                dist[v][p_new] = total_time
                heapq.heappush(heap, (total_time, v, p_new))
    
    # According to the problem statement, it's guaranteed to reach N, so this line is a fallback
    print(-1)

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