結果

問題 No.2366 登校
コンテスト
ユーザー LyricalMaestro
提出日時 2026-08-02 02:16:19
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
MLE  
実行時間 -
コード長 2,105 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 260 ms
コンパイル使用メモリ 96,236 KB
実行使用メモリ 785,500 KB
最終ジャッジ日時 2026-08-02 02:16:28
合計ジャッジ時間 7,648 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 MLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/2366

from collections import deque

MAX_INT = 10 ** 18

def main():
    N, M, K,T = map(int, input().split())
    ab_map = [[None for _ in range(M)] for _ in range(N)]
    for _ in range(K):
        a, b, c, d = map(int, input().split())
        if c > 1:
            ab_map[a - 1][b - 1] =(c - 1, d)

    answer = MAX_INT
    dp = [[{} for _ in range(M)] for _ in range(N)]
    dp[0][0][(0, 0)] = 0
    queue = deque()
    queue.append((0, 0, 0, 0))
    while len(queue) > 0:
        n, m, revert_time, stress = queue.popleft()

        d = dp[n][m][(revert_time, stress)]

        for dn, dm in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            new_n = dn + n
            new_m = dm + m
            if 0 <= new_n < N and 0 <= new_m < M:
                new_state = (revert_time, stress)
                if new_state not in dp[new_n][new_m] or dp[new_n][new_m][new_state] > d + 1:
                    dp[new_n][new_m][new_state] = d + 1
                    queue.append((new_n, new_m, revert_time, stress))

        if ab_map[n][m] is not None:
            c_, d_ = ab_map[n][m]
            new_revert_time = revert_time + c_
            new_stress = stress + d_
            if new_revert_time >= N - 1 + M - 1:
                if d - new_revert_time + (N - 1 - n + M - 1 - m) <= T:
                    answer = min(answer ,new_stress)
            else:
                if d - new_revert_time + (N - 1 - n + M - 1 - m) <= T:
                    answer = min(answer ,new_stress)
                else:
                    new_state = (new_revert_time, new_stress)
                    if new_state not in dp[n][m] or dp[n][m][new_state] > d:
                        dp[n][m][new_state] = d
                        queue.appendleft((n, m, new_revert_time, new_stress))

    for key_state, t in dp[-1][-1].items():
        revert_time, stress = key_state
        if t - revert_time <= T:
            answer = min(answer, stress)

    if answer == MAX_INT:
        print(-1)
    else:
        print(answer)
    




                





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