結果

問題 No.2366 登校
ユーザー lam6er
提出日時 2025-03-31 17:44:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,636 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,436 KB
実行使用メモリ 81,348 KB
最終ジャッジ日時 2025-03-31 17:45:20
合計ジャッジ時間 4,068 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
from collections import deque

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

    myst = {}
    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
        myst[(A, B)] = (C, D)

    # Precompute s_ij: minimal steps from (i,j) to (N-1, M-1)
    s_ij = [[-1]*M for _ in range(N)]
    q = deque()
    end_i = N-1
    end_j = M-1
    q.append((end_i, end_j))
    s_ij[end_i][end_j] = 0
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        i, j = q.popleft()
        for di, dj in dirs:
            ni = i + di
            nj = j + dj
            if 0 <= ni < N and 0 <= nj < M and s_ij[ni][nj] == -1:
                s_ij[ni][nj] = s_ij[i][j] + 1
                q.append((ni, nj))

    if s_ij[0][0] == -1:
        print(-1)
        return

    visited = [[[] for _ in range(M)] for _ in range(N)]
    heap = []
    start_fatigue = 0
    start_time = 0
    heapq.heappush(heap, (start_fatigue, start_time, 0, 0))
    visited[0][0].append( (start_time, start_fatigue) )
    minimal_answer = float('inf')

    best_step = s_ij[0][0]
    if best_step <= T:
        print(0)
        return

    while heap:
        f, t, i, j = heapq.heappop(heap)
        if i == end_i and j == end_j:
            if t <= T:
                print(f)
                return

        s = s_ij[i][j]
        if s == -1:
            continue

        current_needed_time = t + s
        if current_needed_time <= T:
            if f < minimal_answer:
                minimal_answer = f

        if (i,j) in myst:
            C_i, D_i = myst[(i,j)]
            if C_i > 2:
                if s != -1:
                    required_time = t + s
                    if required_time > T:
                        needed = required_time - T
                        divisor = C_i -2
                        k = (needed + divisor -1) // divisor
                        k = max(k, 0)
                        new_time = t + k * (2 - C_i)
                        new_fatigue = f + k * D_i
                        if new_time + s <= T:
                            if new_fatigue < minimal_answer:
                                minimal_answer = new_fatigue
                    else:
                        if f < minimal_answer:
                            minimal_answer = f

        if f >= minimal_answer:
            continue

        for di, dj in dirs:
            ni = i + di
            nj = j + dj
            if 0 <= ni < N and 0 <= nj < M:
                new_time = t +1
                new_fatigue = f
                dominated = False
                vis_list = visited[ni][nj]
                for (t_prev, f_prev) in vis_list:
                    if t_prev <= new_time and f_prev <= new_fatigue:
                        dominated = True
                        break
                if not dominated:
                    new_vis = []
                    add = True
                    for (t_exist, f_exist) in vis_list:
                        if t_exist >= new_time and f_exist >= new_fatigue:
                            continue
                        new_vis.append( (t_exist, f_exist) )
                    new_vis.append( (new_time, new_fatigue) )
                    new_vis.sort()
                    visited[ni][nj] = new_vis
                    heapq.heappush(heap, (new_fatigue, new_time, ni, nj))

        if (i,j) in myst:
            C_i, D_i = myst[(i,j)]
            new_time = t + (2 - C_i)
            new_fatigue = f + D_i
            ni, nj = i, j
            dominated = False
            vis_list = visited[ni][nj]
            for (t_prev, f_prev) in vis_list:
                if t_prev <= new_time and f_prev <= new_fatigue:
                    dominated = True
                    break
            if not dominated:
                new_vis = []
                add = True
                for (t_exist, f_exist) in vis_list:
                    if t_exist >= new_time and f_exist >= new_fatigue:
                        continue
                    new_vis.append( (t_exist, f_exist) )
                new_vis.append( (new_time, new_fatigue) )
                new_vis.sort()
                visited[ni][nj] = new_vis
                heapq.heappush(heap, (new_fatigue, new_time, ni, nj))

    if minimal_answer == float('inf'):
        print(-1)
    else:
        print(minimal_answer)

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