結果

問題 No.614 壊れたキャンパス
ユーザー lam6er
提出日時 2025-04-16 15:47:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,502 bytes
コンパイル時間 372 ms
コンパイル使用メモリ 81,956 KB
実行使用メモリ 189,360 KB
最終ジャッジ日時 2025-04-16 15:48:31
合計ジャッジ時間 5,417 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

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
    
    bridges = [[] for _ in range(n+1)]  # 1-based
    for _ in range(m):
        a = int(data[idx]); idx +=1
        b = int(data[idx]); idx +=1
        c = int(data[idx]); idx +=1
        bridges[a].append( (b, c) )
    
    # Initialize for building 1
    current_sorted = [s]
    current_cost = {s: 0}
    
    for building in range(1, n):
        next_nodes = defaultdict(lambda: float('inf'))
        if not current_sorted:
            break  # No more reachable buildings
        
        # Process each bridge in the current building
        for b_j, c_j in bridges[building]:
            # Find candidates in current_sorted closest to b_j
            pos = bisect.bisect_left(current_sorted, b_j)
            candidates = []
            if pos > 0:
                candidates.append(current_sorted[pos-1])
            if pos < len(current_sorted):
                candidates.append(current_sorted[pos])
            
            min_cost = float('inf')
            for x in candidates:
                cost = current_cost[x] + abs(x - b_j)
                if cost < min_cost:
                    min_cost = cost
            
            if min_cost != float('inf'):
                if min_cost < next_nodes[c_j]:
                    next_nodes[c_j] = min_cost
        
        # Prepare next building's sorted and cost
        if not next_nodes:
            current_sorted = []
            current_cost = {}
        else:
            sorted_x = sorted(next_nodes.keys())
            new_sorted = []
            new_cost = {}
            for x in sorted_x:
                cost = next_nodes[x]
                if x not in new_cost or cost < new_cost[x]:
                    new_cost[x] = cost
                    new_sorted.append(x)
            current_sorted = new_sorted
            current_cost = new_cost
    
    # Check the last building (n)
    if not current_sorted:
        print(-1)
    else:
        min_total = float('inf')
        for x in current_sorted:
            total = current_cost[x] + abs(x - t)
            if total < min_total:
                min_total = total
        print(min_total if min_total != float('inf') else -1)

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