結果

問題 No.2366 登校
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:11:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,021 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,060 KB
実行使用メモリ 157,024 KB
最終ジャッジ日時 2025-06-12 18:13:29
合計ジャッジ時間 6,163 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    magic = {}
    for _ in range(K):
        A = int(input[idx]); idx +=1
        B = int(input[idx]); idx +=1
        C = int(input[idx]); idx +=1
        D = int(input[idx]); idx +=1
        magic[(A, B)] = (C, D)
    
    S = (N-1) + (M-1)
    if S <= T:
        print(0)
        return
    
    # Initialize distance structure
    dist = [ [{} for _ in range(M+1)] for _ in range(N+1) ]
    heap = []
    heapq.heappush(heap, (0, 1, 1, 0))
    dist[1][1][0] = 0

    while heap:
        f, i, j, t = heapq.heappop(heap)
        if i == N and j == M and t <= T:
            print(f)
            return
        
        if t > T:
            continue
        
        # Check if current state is outdated
        current = dist[i][j].get(t, None)
        if current is not None and current < f:
            continue
        
        # Move to adjacent cells
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        for di, dj in directions:
            ni = i + di
            nj = j + dj
            if 1 <= ni <= N and 1 <= nj <= M:
                new_t = t + 1
                if new_t > T:
                    continue
                if new_t not in dist[ni][nj] or f < dist[ni][nj].get(new_t, float('inf')):
                    dist[ni][nj][new_t] = f
                    heapq.heappush(heap, (f, ni, nj, new_t))
        
        # Use magic cell if current cell is magic
        if (i, j) in magic:
            C, D = magic[(i, j)]
            new_t = t + 2 - C
            new_f = f + D
            if new_t > T:
                continue
            if new_t not in dist[i][j] or new_f < dist[i][j].get(new_t, float('inf')):
                dist[i][j][new_t] = new_f
                heapq.heappush(heap, (new_f, i, j, new_t))
    
    print(-1)

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