結果

問題 No.2366 登校
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:57:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,735 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 93,660 KB
最終ジャッジ日時 2025-06-12 20:00:26
合計ジャッジ時間 3,383 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

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

    S = N + M - 2
    if S <= T:
        print(0)
        return

    R = S - T

    myster = {}
    for _ in range(K):
        a = int(data[idx])
        idx += 1
        b = int(data[idx])
        idx += 1
        c = int(data[idx])
        idx += 1
        d = int(data[idx])
        idx += 1
        myster[(a, b)] = (c, d)

    INF = float('inf')
    fatigue = [[[INF] * (R + 1) for _ in range(M + 1)] for __ in range(N + 1)]
    fatigue[1][1][0] = 0

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

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

    found = False
    while heap:
        f, x, y, g = heapq.heappop(heap)
        if x == N and y == M and g >= R:
            print(f)
            found = True
            break
        if f > fatigue[x][y][g]:
            continue
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            if 1 <= nx <= N and 1 <= ny <= M:
                if fatigue[nx][ny][g] > f:
                    fatigue[nx][ny][g] = f
                    heapq.heappush(heap, (f, nx, ny, g))
        if (x, y) in myster:
            c, d = myster[(x, y)]
            gain = c - 1
            if gain <= 0:
                continue
            new_g = min(g + gain, R)
            new_f = f + d
            if new_f < fatigue[x][y][new_g]:
                fatigue[x][y][new_g] = new_f
                heapq.heappush(heap, (new_f, x, y, new_g))

    if not found:
        print(-1)

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