結果

問題 No.2366 登校
ユーザー lam6er
提出日時 2025-04-16 16:22:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,718 bytes
コンパイル時間 624 ms
コンパイル使用メモリ 81,552 KB
実行使用メモリ 82,504 KB
最終ジャッジ日時 2025-04-16 16:23:49
合計ジャッジ時間 4,977 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    N, M, K, T = map(int, input().split())
    magic_cells = {}
    for _ in range(K):
        A, B, C, D = map(int, input().split())
        magic_cells[(A, B)] = (C, D)
    
    dirs = [ (-1,0), (1,0), (0,-1), (0,1) ]
    
    state_map = [ [ [] for _ in range(M+1) ] for _ in range(N+1) ]
    heap = []
    heapq.heappush(heap, (0, 1, 1, 0, 0))
    state_map[1][1].append((0, 0, 0))
    
    found = False
    answer = -1
    
    while heap:
        fatigue, i, j, s, r = heapq.heappop(heap)
        
        if i == N and j == M:
            if r >= s - T:
                answer = fatigue
                found = True
                break
        
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 1 <= ni <= N and 1 <= nj <= M:
                new_s = s + 1
                new_r = r
                new_fatigue = fatigue
                
                dominated = False
                for (es, er, ef) in state_map[ni][nj]:
                    if es <= new_s and er >= new_r:
                        dominated = True
                        break
                if dominated:
                    continue
                
                new_entries = []
                add_new = True
                for entry in state_map[ni][nj]:
                    es, er, ef_entry = entry
                    if es >= new_s and er <= new_r:
                        continue
                    if es <= new_s and er >= new_r:
                        add_new = False
                        break
                    new_entries.append(entry)
                if not add_new:
                    continue
                
                for entry in new_entries:
                    es, er, ef_entry = entry
                    if es <= new_s and er >= new_r:
                        add_new = False
                        break
                if not add_new:
                    continue
                
                new_entries.append((new_s, new_r, new_fatigue))
                new_entries.sort()
                state_map[ni][nj] = new_entries
                heapq.heappush(heap, (new_fatigue, ni, nj, new_s, new_r))
        
        if (i, j) in magic_cells:
            C, D = magic_cells[(i, j)]
            new_s_rewind = s + 1
            new_r_rewind = r + (C - 1)
            new_fatigue_rewind = fatigue + D
            
            dominated = False
            for (es, er, ef) in state_map[i][j]:
                if es <= new_s_rewind and er >= new_r_rewind:
                    dominated = True
                    break
            if dominated:
                continue
            
            new_entries = []
            add_new = True
            for entry in state_map[i][j]:
                es, er, ef_entry = entry
                if es >= new_s_rewind and er <= new_r_rewind:
                    continue
                if es <= new_s_rewind and er >= new_r_rewind:
                    add_new = False
                    break
                new_entries.append(entry)
            if not add_new:
                continue
            
            for entry in new_entries:
                es, er, ef_entry = entry
                if es <= new_s_rewind and er >= new_r_rewind:
                    add_new = False
                    break
            if not add_new:
                continue
            
            new_entries.append((new_s_rewind, new_r_rewind, new_fatigue_rewind))
            new_entries.sort()
            state_map[i][j] = new_entries
            heapq.heappush(heap, (new_fatigue_rewind, i, j, new_s_rewind, new_r_rewind))
    
    print(answer if found else -1)

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