結果

問題 No.2366 登校
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:22:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,254 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,072 KB
実行使用メモリ 79,464 KB
最終ジャッジ日時 2025-04-16 00:24:06
合計ジャッジ時間 3,272 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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

    mysterious = {}
    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)

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

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

    cell_info = [[[] for _ in range(m)] for _ in range(n)]

    found = False
    answer = -1

    while heap:
        fatigue, time, i, j = heapq.heappop(heap)

        if i == n-1 and j == m-1:
            if time <= T:
                answer = fatigue
                found = True
                break
            else:
                continue

        dominated = False
        for (t, f) in cell_info[i][j]:
            if t <= time and f <= fatigue:
                dominated = True
                break
        if dominated:
            continue

        cell_info[i][j].append( (time, fatigue) )

        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < m:
                new_time = time + 1
                new_fatigue = fatigue
                if new_time > T:
                    continue
                dom = False
                for (t, f) in cell_info[ni][nj]:
                    if t <= new_time and f <= new_fatigue:
                        dom = True
                        break
                if not dom:
                    heapq.heappush(heap, (new_fatigue, new_time, ni, nj))

        if (i, j) in mysterious:
            c, d = mysterious[(i, j)]
            new_time = time + (2 - c)
            new_fatigue = fatigue + d
            if new_time > T:
                continue
            dom = False
            for (t, f) in cell_info[i][j]:
                if t <= new_time and f <= new_fatigue:
                    dom = True
                    break
            if not dom:
                heapq.heappush(heap, (new_fatigue, new_time, i, j))

    print(answer if found else -1)

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