結果

問題 No.614 壊れたキャンパス
ユーザー lam6er
提出日時 2025-03-31 17:49:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,649 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 170,112 KB
最終ジャッジ日時 2025-03-31 17:50:20
合計ジャッジ時間 6,888 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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
    
    edges = [[] for _ in range(n)]
    for _ in range(m):
        a = int(data[idx]) - 1; idx += 1  # convert to 0-based
        b = int(data[idx]); idx += 1
        c = int(data[idx]); idx += 1
        edges[a].append((b, c))
    
    # Initialize buildings' points. Each building's points are kept in a sorted list of tuples (x, cost)
    buildings = [[] for _ in range(n)]
    if S < 1 or S > K:
        print(-1)
        return
    buildings[0] = [(S, 0)]  # (x, cost)
    
    for i in range(n-1):
        current = buildings[i]
        if not current:
            continue
        next_points = []
        # Collect all transitions via sky bridges from current building to next
        for (b, c) in edges[i]:
            # Find the minimal cost to reach b in current building
            min_cost = float('inf')
            idx_b = bisect.bisect_left(current, (b, -1))
            # Check possible candidates around idx_b
            candidates = []
            if idx_b > 0:
                candidates.append(idx_b - 1)
            if idx_b < len(current):
                candidates.append(idx_b)
            for pos in candidates:
                x, cost_x = current[pos]
                total_cost = cost_x + abs(x - b)
                if total_cost < min_cost:
                    min_cost = total_cost
            if min_cost != float('inf'):
                next_points.append((c, min_cost))
        # Merge next_points into buildings[i+1] with optimal points
        next_building = []
        # Process each new point and merge into next_building
        for x, cost in next_points:
            # Insert x with cost into next_building, removing dominated points
            # First check if x is already present with lower cost
            insert_pos = bisect.bisect_left(next_building, (x, -1))
            if insert_pos < len(next_building) and next_building[insert_pos][0] == x:
                if next_building[insert_pos][1] <= cost:
                    continue  # existing cost is better
                else:
                    next_building.pop(insert_pos)
            # Insert (x, cost) and maintain the list
            bisect.insort(next_building, (x, cost))
            pos = bisect.bisect_left(next_building, (x, cost))
            # Check previous points to see if current point can dominate them
            # Check left
            while pos > 0:
                prev_pos = pos - 1
                prev_x, prev_cost = next_building[prev_pos]
                if prev_cost + (x - prev_x) >= cost:
                    next_building.pop(prev_pos)
                    pos -= 1
                else:
                    break
            # Check right
            while pos < len(next_building) - 1:
                next_pos = pos + 1
                next_x, next_cost = next_building[next_pos]
                if next_cost + (next_x - x) >= cost:
                    next_building.pop(next_pos)
                else:
                    break
        buildings[i+1] = next_building
    
    # Process the final building
    final = buildings[-1]
    if not final:
        print(-1)
        return
    min_total = float('inf')
    for x, cost in final:
        total = cost + 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