結果

問題 No.2366 登校
コンテスト
ユーザー LyricalMaestro
提出日時 2026-08-02 02:18:55
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 2,103 ms / 4,000 ms
+ 542µs
コード長 2,229 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 244 ms
コンパイル使用メモリ 96,236 KB
実行使用メモリ 346,104 KB
最終ジャッジ日時 2026-08-02 02:19:27
合計ジャッジ時間 7,042 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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 answer >= new_stress:
                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