結果

問題 No.614 壊れたキャンパス
ユーザー lam6er
提出日時 2025-04-15 22:04:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 478 ms / 2,000 ms
コード長 2,879 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 81,768 KB
実行使用メモリ 195,436 KB
最終ジャッジ日時 2025-04-15 22:05:17
合計ジャッジ時間 5,927 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

    bridges = [[] for _ in range(N+1)]  # bridges[a] contains list of (b, c)
    for _ in range(M):
        a = int(input[ptr])
        ptr +=1
        b = int(input[ptr])
        ptr +=1
        c = int(input[ptr])
        ptr +=1
        bridges[a].append( (b, c) )

    # Initialize buildings. Each building has a dictionary of x: cost
    buildings = [dict() for _ in range(N+2)]  # 1-based
    buildings[1][S] = 0

    for i in range(1, N):
        if not bridges[i]:
            continue
        if not buildings[i]:
            continue
        # Process building i's bridges
        # Sort the x's in building i
        sorted_x = sorted(buildings[i].items(), key=lambda x: x[0])
        x_list = [x for x, cost in sorted_x]
        cost_list = [cost for x, cost in sorted_x]
        n = len(x_list)
        if n == 0:
            continue

        # Compute prefix minima (cost[x] - x)
        prefix_min = [0]*n
        prefix_min[0] = cost_list[0] - x_list[0]
        for j in range(1, n):
            prefix_min[j] = min(prefix_min[j-1], cost_list[j] - x_list[j])

        # Compute suffix minima (cost[x] + x)
        suffix_min = [0]*n
        suffix_min[-1] = cost_list[-1] + x_list[-1]
        for j in range(n-2, -1, -1):
            suffix_min[j] = min(suffix_min[j+1], cost_list[j] + x_list[j])

        # Process each bridge in building i
        for b, c in bridges[i]:
            # Find the minimal cost to reach b in building i
            # Binary search for the largest x <= b
            pos = bisect.bisect_right(x_list, b) -1
            min_left = float('inf')
            if pos >=0:
                min_left = prefix_min[pos] + b

            # Binary search for the smallest x >= b
            pos2 = bisect.bisect_left(x_list, b)
            min_right = float('inf')
            if pos2 < n:
                min_right = suffix_min[pos2] - b

            current_cost = min(min_left, min_right)
            if current_cost == float('inf'):
                continue

            # Update building i+1's c
            if c in buildings[i+1]:
                if current_cost < buildings[i+1][c]:
                    buildings[i+1][c] = current_cost
            else:
                buildings[i+1][c] = current_cost

    # Check building N
    if not buildings[N]:
        print(-1)
    else:
        min_total = float('inf')
        for x, cost in buildings[N].items():
            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