結果

問題 No.2366 登校
ユーザー gew1fw
提出日時 2025-06-12 12:53:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,319 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 75,008 KB
最終ジャッジ日時 2025-06-12 12:54:30
合計ジャッジ時間 2,658 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def bfs(n, m, start):
    dist = [[-1] * (m + 1) for _ in range(n + 1)]
    q = deque()
    sx, sy = start
    dist[sx][sy] = 0
    q.append((sx, sy))
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        x, y = q.popleft()
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            if 1 <= nx <= n and 1 <= ny <= m and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    return dist

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]); idx +=1
        B = int(input[idx]); idx +=1
        C = int(input[idx]); idx +=1
        D = int(input[idx]); idx +=1
        mysterious.append( (A, B, C, D) )

    # Compute shortest distance from start (1,1)
    dist_start = bfs(N, M, (1,1))
    # Compute shortest distance from goal (N,M)
    dist_goal = bfs(N, M, (N, M))

    # Check if the normal path is possible
    S = dist_start[N][M]
    if S == -1:
        print(-1)
        return
    if S <= T:
        print(0)
        return

    min_fatigue = float('inf')

    for (A, B, C, D) in mysterious:
        a = dist_start[A][B]
        b = dist_goal[A][B]
        if a == -1 or b == -1:
            continue  # Cannot reach this cell or cannot reach goal from this cell
        total_time = a + b
        save_needed = total_time - T
        if save_needed <= 0:
            continue  # No need to use this cell
        save_per_op = C - 1
        if save_per_op <= 0:
            continue  # No time saved per operation
        # Calculate minimum k
        k_min = (save_needed + save_per_op - 1) // save_per_op
        # Check if after k_min operations, time is within T
        new_time = total_time - k_min * save_per_op
        if new_time > T:
            continue  # Not sufficient, though this shouldn't happen with correct k_min
        fatigue = k_min * D
        if fatigue < min_fatigue:
            min_fatigue = fatigue

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

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