結果

問題 No.614 壊れたキャンパス
ユーザー lam6er
提出日時 2025-03-20 20:42:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,133 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 361,260 KB
最終ジャッジ日時 2025-03-20 20:42:40
合計ジャッジ時間 23,826 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from heapq import heappush, heappop
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    M = int(input[idx]); idx += 1
    K = int(input[idx]); idx += 1
    S = int(input[idx]); idx += 1
    T = int(input[idx]); idx += 1

    bridges = []
    for _ in range(M):
        a = int(input[idx]); idx += 1
        b = int(input[idx]); idx += 1
        c = int(input[idx]); idx += 1
        bridges.append((a, b, c))

    # Initialize important floors for each building
    building_floors = [[] for _ in range(N + 2)]  # 1-based indexing
    building_floors[1].append(S)
    building_floors[N].append(T)
    for a, b, c in bridges:
        building_floors[a].append(b)
        building_floors[a + 1].append(c)

    # Sort and deduplicate each building's floors
    for j in range(1, N + 1):
        floors = building_floors[j]
        floors = sorted(list(set(floors)))
        building_floors[j] = floors

    # Build adjacency list
    adj = defaultdict(list)
    for j in range(1, N + 1):
        floors = building_floors[j]
        for i in range(len(floors) - 1):
            f_prev = floors[i]
            f_next = floors[i + 1]
            delta = f_next - f_prev
            adj[(j, f_prev)].append(((j, f_next), delta))
            adj[(j, f_next)].append(((j, f_prev), delta))

    # Add bridge edges
    for a, b, c in bridges:
        adj[(a, b)].append(((a + 1, c), 0))

    # Dijkstra's algorithm
    dist = defaultdict(lambda: float('inf'))
    start = (1, S)
    dist[start] = 0
    heap = []
    heappush(heap, (0, 1, S))

    target = (N, T)

    while heap:
        current_cost, j, f = heappop(heap)
        if (j, f) == target:
            print(current_cost)
            return
        if current_cost > dist[(j, f)]:
            continue
        for (nj, nf), delta in adj.get((j, f), []):
            new_cost = current_cost + delta
            if new_cost < dist[(nj, nf)]:
                dist[(nj, nf)] = new_cost
                heappush(heap, (new_cost, nj, nf))

    print(-1)

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