結果

問題 No.614 壊れたキャンパス
ユーザー lam6er
提出日時 2025-04-15 22:03:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,717 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 158,240 KB
最終ジャッジ日時 2025-04-15 22:04:55
合計ジャッジ時間 12,473 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
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 = defaultdict(list)
    for _ in range(M):
        a = int(input[idx]); idx += 1
        b = int(input[idx]); idx += 1
        c = int(input[idx]); idx += 1
        bridges[a].append((b, c))

    current = [(0, S)]

    for i in range(1, N):
        if not current:
            break
        bs = bridges.get(i, [])
        temp_next = []
        for b, c_j in bs:
            for m, curr_c in current:
                new_m = m + abs(curr_c - b)
                temp_next.append((new_m, c_j))
        
        next_building = []
        for m_new, c_new in temp_next:
            add = True
            to_remove = []
            for idx_ex, (m_ex, c_ex) in enumerate(next_building):
                if m_new + abs(c_new - c_ex) <= m_ex:
                    to_remove.append(idx_ex)
                elif m_ex + abs(c_ex - c_new) <= m_new:
                    add = False
                    break
            if not add:
                continue
            new_list = []
            for idx_ex, (m_ex, c_ex) in enumerate(next_building):
                if idx_ex not in to_remove:
                    new_list.append((m_ex, c_ex))
            new_list.append((m_new, c_new))
            next_building = new_list
        
        current = next_building

    if not current:
        print(-1)
    else:
        min_cost = min(m + abs(c - T) for m, c in current)
        print(min_cost)

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