結果

問題 No.2366 登校
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:35:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,861 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 78,888 KB
最終ジャッジ日時 2025-04-15 23:36:52
合計ジャッジ時間 2,706 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

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

    cells = []
    for _ in range(K):
        A = int(input[idx])-1; idx +=1  # converting to 0-based
        B = int(input[idx])-1; idx +=1
        C = int(input[idx]); idx +=1
        D = int(input[idx]); idx +=1
        cells.append( (A,B,C,D) )

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

    required = D_min - T

    # BFS from (0,0) to all cells
    d1 = [[-1]*M for _ in range(N)]
    q = deque()
    q.append( (0,0) )
    d1[0][0] = 0
    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 0<=nx<N and 0<=ny<M and d1[nx][ny] == -1:
                d1[nx][ny] = d1[x][y] +1
                q.append( (nx, ny) )

    # BFS from (N-1, M-1) to all cells (reverse)
    d2 = [[-1]*M for _ in range(N)]
    q = deque()
    q.append( (N-1, M-1) )
    d2[N-1][M-1] =0
    while q:
        x,y = q.popleft()
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            if 0<=nx<N and 0<=ny<M and d2[nx][ny] == -1:
                d2[nx][ny] = d2[x][y] +1
                q.append( (nx, ny) )

    min_sum = float('inf')
    for (A,B,C,D) in cells:
        if d1[A][B] == -1 or d2[A][B] == -1:
            continue
        delta = C -1
        if delta <=0:
            continue
        k = (required + delta -1) // delta  # ceil(required/delta)
        sum_D = k * D
        if sum_D < min_sum:
            min_sum = sum_D

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

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