結果

問題 No.2366 登校
ユーザー lam6er
提出日時 2025-04-16 16:46:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,568 bytes
コンパイル時間 576 ms
コンパイル使用メモリ 81,500 KB
実行使用メモリ 80,400 KB
最終ジャッジ日時 2025-04-16 16:49:12
合計ジャッジ時間 2,989 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

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
    K = int(input[idx]); idx +=1
    T = int(input[idx]); idx +=1

    mysterious = dict()
    for _ in range(K):
        A = int(input[idx])-1; idx +=1
        B = int(input[idx])-1; idx +=1
        C = int(input[idx]); idx +=1
        D = int(input[idx]); idx +=1
        mysterious[(A,B)] = (C, D)

    start = (0, 0)
    end = (N-1, M-1)

    # Dijkstra's priority queue: (fatigue, current_time, i, j)
    heap = []
    heapq.heappush(heap, (0, 0, start[0], start[1]))

    # For each cell, keep a list of (fatigue, time) sorted by fatigue
    # To check if a new state is not dominated
    cell_states = [[dict() for _ in range(M)] for _ in range(N)]
    cell_states[start[0]][start[1]][0] = 0

    found = False
    answer = -1

    dirs = [(-1,0), (1,0), (0,-1), (0,1)]

    while heap:
        f, t, i, j = heapq.heappop(heap)

        if (i, j) == end:
            if t <= T:
                answer = f
                found = True
                break
            else:
                continue

        if cell_states[i][j].get(f, float('inf')) < t:
            continue

        # Move to adjacent cells
        for di, dj in dirs:
            ni = i + di
            nj = j + dj
            if 0 <= ni < N and 0 <= nj < M:
                new_t = t + 1
                new_f = f
                if new_t > T:
                    continue
                # Check if this state is dominated
                add = True
                to_remove = []
                current_fatigues = cell_states[ni][nj]
                for existing_f in list(current_fatigues.keys()):
                    existing_t = current_fatigues[existing_f]
                    if existing_f <= new_f and existing_t <= new_t:
                        add = False
                        break
                    if existing_f >= new_f and existing_t >= new_t:
                        to_remove.append(existing_f)
                if add:
                    for fr in to_remove:
                        del current_fatigues[fr]
                    if new_f not in current_fatigues or new_t < current_fatigues.get(new_f, float('inf')):
                        current_fatigues[new_f] = new_t
                        heapq.heappush(heap, (new_f, new_t, ni, nj))

        # Use mysterious square if present
        if (i, j) in mysterious:
            C, D = mysterious[(i,j)]
            new_t = t + (2 - C)
            new_f = f + D
            if new_t > T:
                continue
            # Check if this state is dominated
            add = True
            to_remove = []
            current_fatigues = cell_states[i][j]
            for existing_f in list(current_fatigues.keys()):
                existing_t = current_fatigues[existing_f]
                if existing_f <= new_f and existing_t <= new_t:
                    add = False
                    break
                if existing_f >= new_f and existing_t >= new_t:
                    to_remove.append(existing_f)
            if add:
                for fr in to_remove:
                    if fr in current_fatigues:
                        del current_fatigues[fr]
                if new_f not in current_fatigues or new_t < current_fatigues.get(new_f, float('inf')):
                    current_fatigues[new_f] = new_t
                    heapq.heappush(heap, (new_f, new_t, i, j))

    print(answer if found else -1)

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