結果

問題 No.1283 Extra Fee
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:26:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,735 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 189 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 123,780 KB
最終ジャッジ日時 2025-03-20 20:28:08
合計ジャッジ時間 6,033 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq

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

    fees = {}
    for _ in range(M):
        h = int(input[idx])
        idx += 1
        w = int(input[idx])
        idx += 1
        c = int(input[idx])
        idx += 1
        fees[(h, w)] = c

    heap = []
    heapq.heappush(heap, (0, 1, 1, 0, 0))  # (cost, h, w, state, max_fee)
    visited0 = {}  # Key: (h, w), Value: {max_fee: minimal_cost}
    d1 = [[float('inf')] * (N + 2) for _ in range(N + 2)]  # state 1's cost

    answer = float('inf')

    while heap:
        current_cost, h, w, state, current_max = heapq.heappop(heap)
        if h == N and w == N:
            answer = min(answer, current_cost)
            continue  # Continue to find better paths

        if state == 0:
            if (h, w) not in visited0:
                visited0[(h, w)] = {}
            valid = True
            # Check if any existing entry with higher or equal max and lower or equal cost
            keys = list(visited0[(h, w)].keys())
            for existing_max in keys:
                existing_cost = visited0[(h, w)][existing_max]
                if existing_max >= current_max and existing_cost <= current_cost:
                    valid = False
                    break
            if not valid:
                continue
            # Remove dominated entries (existing_max <= current_max and existing_cost >= current_cost)
            to_remove = []
            for existing_max in keys:
                existing_cost = visited0[(h, w)][existing_max]
                if existing_max <= current_max and existing_cost >= current_cost:
                    to_remove.append(existing_max)
            for k in to_remove:
                del visited0[(h, w)][k]
            # Add current entry
            if current_max in visited0[(h, w)]:
                if current_cost < visited0[(h, w)][current_max]:
                    visited0[(h, w)][current_max] = current_cost
            else:
                visited0[(h, w)][current_max] = current_cost

            # Generate state 0 transitions
            for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nh = h + dh
                nw = w + dw
                if 1 <= nh <= N and 1 <= nw <= N:
                    fee = fees.get((nh, nw), 0)
                    new_cost0 = current_cost + 1  # Step cost
                    if (nh, nw) in fees:
                        new_cost0 += fee
                    new_max = current_max
                    if (nh, nw) in fees:
                        new_max = max(new_max, fee)
                    # Push state 0 transition
                    heapq.heappush(heap, (new_cost0, nh, nw, 0, new_max))
                    # Generate state 1 transition (using skip)
                    new_max_skip = new_max
                    new_cost1 = current_cost + 1
                    if (nh, nw) in fees:
                        new_cost1 += fee
                    new_cost1 -= new_max_skip
                    heapq.heappush(heap, (new_cost1, nh, nw, 1, 0))
        else:
            # State 1: do not track max_fee anymore
            if current_cost >= d1[h][w]:
                continue
            d1[h][w] = current_cost
            for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nh = h + dh
                nw = w + dw
                if 1 <= nh <= N and 1 <= nw <= N:
                    fee = fees.get((nh, nw), 0)
                    new_cost1 = current_cost + 1 + fee
                    if new_cost1 < d1[nh][nw]:
                        d1[nh][nw] = new_cost1
                        heapq.heappush(heap, (new_cost1, nh, nw, 1, 0))
        # Early exit if both queues have reached (N,N)
        # However, since heapq doesn't allow peeking, proceed until empty

    if answer != float('inf'):
        print(answer)
    else:
        # If all fees are skipped and path has none
        # Compute the normal BFS without fees
        from collections import deque
        visited = [[False]*(N+1) for _ in range(N+1)]
        q = deque([(1, 1, 0)])
        visited[1][1] = True
        found = False
        while q:
            h, w, steps = q.popleft()
            if h == N and w == N:
                print(steps)
                found = True
                break
            for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nh = h + dh
                nw = w + dw
                if 1 <= nh <= N and 1 <= nw <= N and not visited[nh][nw]:
                    visited[nh][nw] = True
                    q.append((nh, nw, steps+1))
        if not found:
            print(-1)

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