結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    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

    # Read mysterious squares
    mysterious = []
    for _ in range(K):
        A = int(input[ptr])-1; ptr +=1 # convert to 0-based
        B = int(input[ptr])-1; ptr +=1
        C = int(input[ptr]); ptr +=1
        D = int(input[ptr]); ptr +=1
        mysterious.append( (A, B, C, D) )

    # Compute dist_start: minimal steps from (0,0)
    dist_start = [ [ -1 for _ in range(M) ] for __ in range(N) ]
    q = deque()
    q.append( (0,0) )
    dist_start[0][0] = 0
    while q:
        i,j = q.popleft()
        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 and dist_start[ni][nj] == -1:
                dist_start[ni][nj] = dist_start[i][j] +1
                q.append( (ni, nj) )

    # Compute dist_end: minimal steps from (N-1, M-1)
    dist_end = [ [ -1 for _ in range(M) ] for __ in range(N) ]
    q = deque()
    q.append( (N-1, M-1) )
    dist_end[N-1][M-1] = 0
    while q:
        i,j = q.popleft()
        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 and dist_end[ni][nj] == -1:
                dist_end[ni][nj] = dist_end[i][j] +1
                q.append( (ni, nj) )

    D = (N-1) + (M-1)
    if D <= T:
        print(0)
        return

    min_fatigue = float('inf')
    for (A, B, C, D_i) in mysterious:
        if C <= 1:
            continue  # No gain, skip
        s_i = A
        s_j = B
        if dist_start[s_i][s_j] == -1 or dist_end[s_i][s_j] == -1:
            continue  # Not reachable, skip
        needed = (dist_start[s_i][s_j] + dist_end[s_i][s_j]) - T
        if needed <= 0:
            continue
        gain = C -1
        if gain <=0:
            continue
        k = (needed + gain -1) // gain  # Ceiling division
        fatigue = k * D_i
        if fatigue < min_fatigue:
            min_fatigue = fatigue

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

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