結果

問題 No.614 壊れたキャンパス
ユーザー lam6er
提出日時 2025-04-16 15:48:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 673 ms / 2,000 ms
コード長 3,443 bytes
コンパイル時間 620 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 156,068 KB
最終ジャッジ日時 2025-04-16 15:49:34
合計ジャッジ時間 6,895 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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)]  # bridges[a] contains list of (b_i, c_i)
    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) )
    
    current = [ (s, 0) ]  # list of (floor, cost) for current building
    
    for a in range(1, n):
        # Optimize current building's state
        current.sort()
        optimized = []
        for f, c in current:
            if not optimized:
                optimized.append( (f, c) )
                continue
            prev_f, prev_c = optimized[-1]
            if prev_c + (f - prev_f) <= c:
                continue  # current point is dominated by previous
            # Check if previous points can be removed
            while optimized and (c + (f - prev_f) <= prev_c):
                optimized.pop()
                if optimized:
                    prev_f, prev_c = optimized[-1]
                else:
                    break
            optimized.append( (f, c) )
        current = optimized
        if not current:
            break  # no way to proceed
        
        # Process all bridges from building a to a+1
        next_points = defaultdict(lambda: float('inf'))
        for b_i, c_i in bridges[a]:
            # Find the closest points in current to b_i
            idx_b = bisect.bisect_left(current, (b_i, -1))
            candidates = []
            if idx_b > 0:
                candidates.append(current[idx_b -1])
            if idx_b < len(current):
                candidates.append(current[idx_b])
            # Check for the minimal cost
            min_cost = float('inf')
            for (f, cost) in candidates:
                total = cost + abs(f - b_i)
                if total < min_cost:
                    min_cost = total
            if min_cost < next_points[c_i]:
                next_points[c_i] = min_cost
        
        # Prepare next building's current state
        next_list = []
        for c_i in next_points:
            next_list.append( (c_i, next_points[c_i]) )
        # Optimize next_list
        next_list.sort()
        optimized_next = []
        for f, c in next_list:
            if not optimized_next:
                optimized_next.append( (f, c) )
                continue
            prev_f, prev_c = optimized_next[-1]
            if prev_c + (f - prev_f) <= c:
                continue  # dominated by previous
            # Check if previous can be removed
            while optimized_next and (c + (f - prev_f) <= prev_c):
                optimized_next.pop()
                if optimized_next:
                    prev_f, prev_c = optimized_next[-1]
                else:
                    break
            optimized_next.append( (f, c) )
        current = optimized_next
    
    if not current:
        print(-1)
    else:
        min_total = float('inf')
        for f, c in current:
            total = c + abs(f - t)
            if total < min_total:
                min_total = total
        print(min_total if min_total != float('inf') else -1)

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