結果

問題 No.2366 登校
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:08:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,384 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 80,488 KB
最終ジャッジ日時 2025-06-12 18:11:06
合計ジャッジ時間 3,707 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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])-1; idx +=1
        B = int(input[idx])-1; idx +=1
        C = int(input[idx]); idx +=1
        D = int(input[idx]); idx +=1
        magic[(A, B)] = (C, D)

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

    heap = []
    heapq.heappush(heap, (0, start[0], start[1], T))

    best = {}
    for i in range(N):
        for j in range(M):
            best[(i, j)] = {}
    best[start][0] = T

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

    while heap:
        f, x, y, t = heapq.heappop(heap)

        if (x, y) == end:
            print(f)
            found = True
            break

        if f not in best.get((x, y), {}) or best[(x, y)].get(f, -1) > t:
            continue

        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < N and 0 <= ny < M:
                new_t = t - 1
                new_f = f
                if new_t < 0:
                    continue
                entry = best.get((nx, ny), {})
                add = True
                for key in list(entry.keys()):
                    if key <= new_f and entry[key] >= new_t:
                        add = False
                        break
                if add:
                    if new_f not in best[(nx, ny)] or best[(nx, ny)][new_f] < new_t:
                        best[(nx, ny)][new_f] = new_t
                        heapq.heappush(heap, (new_f, nx, ny, new_t))

        if (x, y) in magic:
            C, D = magic[(x, y)]
            new_t = t + (C - 2)
            new_f = f + D
            if new_t >= 0:
                entry = best.get((x, y), {})
                add = True
                for key in list(entry.keys()):
                    if key <= new_f and entry[key] >= new_t:
                        add = False
                        break
                if add:
                    if new_f not in best[(x, y)] or best[(x, y)][new_f] < new_t:
                        best[(x, y)][new_f] = new_t
                        heapq.heappush(heap, (new_f, x, y, new_t))

    if not found:
        print(-1)

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