結果

問題 No.614 壊れたキャンパス
ユーザー lam6er
提出日時 2025-04-15 22:00:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,815 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 423,316 KB
最終ジャッジ日時 2025-04-15 22:01:42
合計ジャッジ時間 4,550 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 3 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

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
    K = int(data[idx]); idx +=1
    S = int(data[idx]); idx +=1
    T = int(data[idx]); idx +=1
    
    adj = [[] for _ in range(N+1)]  # adj[i] contains the list of (b_i, c_i) for building i
    for _ in range(M):
        a_i = int(data[idx]); idx +=1
        b_i = int(data[idx]); idx +=1
        c_i = int(data[idx]); idx +=1
        adj[a_i].append( (b_i, c_i) )
    
    INF = 1 << 60
    f = [0]*(N+1)  # optimal floor for each building
    c = [INF]*(N+1)  # minimal cost to reach the optimal floor
    
    # Initialize for building 1
    f[1] = S
    c[1] = 0
    
    heap = []
    heapq.heappush(heap, (0, 1))
    
    while heap:
        current_cost, i = heapq.heappop(heap)
        if current_cost > c[i]:
            continue
        # Process all corridors from building i
        for (b, next_floor) in adj[i]:
            new_cost = c[i] + abs(f[i] - b)
            j = i + 1
            if j > N:
                continue  # should not happen as per input constraints
            # Calculate the current cost to reach next_floor in building j
            current_j_cost = c[j] + abs(f[j] - next_floor)
            if new_cost < current_j_cost:
                if new_cost < c[j]:
                    c[j] = new_cost
                    f[j] = next_floor
                else:
                    # Even if new_cost is not less than c[j], but the path to next_floor is better
                    c[j] = new_cost
                    f[j] = next_floor
                heapq.heappush(heap, (c[j], j))
    
    if c[N] == INF:
        print(-1)
    else:
        print(c[N] + abs(f[N] - T))

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