結果

問題 No.2366 登校
ユーザー gew1fw
提出日時 2025-06-12 14:58:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,029 bytes
コンパイル時間 287 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 83,620 KB
最終ジャッジ日時 2025-06-12 14:59:52
合計ジャッジ時間 3,681 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
import bisect

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

    mysterious = dict()
    for _ in range(K):
        A = int(input[ptr]) - 1; ptr += 1
        B = int(input[ptr]) - 1; ptr += 1
        C = int(input[ptr]); ptr += 1
        D = int(input[ptr]); ptr += 1
        mysterious[(A, B)] = (C, D)

    visited = [[[] for _ in range(M)] for _ in range(N)]
    heap = []
    start_i, start_j = 0, 0
    dest_i, dest_j = N - 1, M - 1

    heapq.heappush(heap, (0, 0, start_i, start_j))
    visited[start_i][start_j].append((0, 0))

    min_fatigue = -1

    while heap:
        f, t, i, j = heapq.heappop(heap)

        if i == dest_i and j == dest_j and t <= T:
            min_fatigue = f
            break

        # Move transitions
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < N and 0 <= nj < M:
                new_t = t + 1
                new_f = f

                dominated = False
                current_list = visited[ni][nj]
                for (prev_t, prev_f) in current_list:
                    if prev_t <= new_t and prev_f <= new_f:
                        dominated = True
                        break
                    if prev_t > new_t:
                        break
                if dominated:
                    continue

                t_list = [pt for pt, _ in current_list]
                insert_pos = bisect.bisect_left(t_list, new_t)

                new_entries = []
                for idx in range(insert_pos):
                    new_entries.append(current_list[idx])

                for idx in range(insert_pos, len(current_list)):
                    pt, pf = current_list[idx]
                    if pf < new_f:
                        new_entries.append((pt, pf))

                new_entries.append((new_t, new_f))
                new_entries.sort()

                valid = True
                for idx in range(len(new_entries)):
                    pt, pf = new_entries[idx]
                    if pt <= new_t and pf <= new_f:
                        if pt != new_t or pf != new_f:
                            valid = False
                            break
                if valid:
                    visited[ni][nj] = new_entries
                    heapq.heappush(heap, (new_f, new_t, ni, nj))

        # Mysterious square transition
        if (i, j) in mysterious:
            C, D = mysterious[(i, j)]
            new_t = t + 2 - C
            new_f = f + D

            dominated = False
            current_list = visited[i][j]
            for (prev_t, prev_f) in current_list:
                if prev_t <= new_t and prev_f <= new_f:
                    dominated = True
                    break
                if prev_t > new_t:
                    break
            if dominated:
                continue

            t_list = [pt for pt, _ in current_list]
            insert_pos = bisect.bisect_left(t_list, new_t)

            new_entries = []
            for idx in range(insert_pos):
                new_entries.append(current_list[idx])

            for idx in range(insert_pos, len(current_list)):
                pt, pf = current_list[idx]
                if pf < new_f:
                    new_entries.append((pt, pf))

            new_entries.append((new_t, new_f))
            new_entries.sort()

            valid = True
            for idx in range(len(new_entries)):
                pt, pf = new_entries[idx]
                if pt <= new_t and pf <= new_f:
                    if pt != new_t or pf != new_f:
                        valid = False
                        break
            if valid:
                visited[i][j] = new_entries
                heapq.heappush(heap, (new_f, new_t, i, j))

    print(min_fatigue if min_fatigue != -1 else -1)

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