結果

問題 No.2366 登校
ユーザー lam6er
提出日時 2025-04-09 20:58:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,181 bytes
コンパイル時間 274 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 78,256 KB
最終ジャッジ日時 2025-04-09 21:00:40
合計ジャッジ時間 2,657 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    # Read input
    N, M, K, T = map(int, sys.stdin.readline().split())
    magic = []
    for _ in range(K):
        A, B, C, D = map(int, sys.stdin.readline().split())
        A -= 1  # convert to 0-based
        B -= 1
        magic.append((A, B, C, D))
    
    # Directions: up, down, left, right
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # BFS from start (0,0)
    start_dist = [[float('inf')] * M for _ in range(N)]
    start_dist[0][0] = 0
    q = deque()
    q.append((0, 0))
    
    while q:
        x, y = q.popleft()
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M:
                if start_dist[nx][ny] > start_dist[x][y] + 1:
                    start_dist[nx][ny] = start_dist[x][y] + 1
                    q.append((nx, ny))
    
    S_min = start_dist[N-1][M-1]
    if S_min <= T:
        print(0)
        return
    
    # BFS from end (N-1, M-1)
    end_dist = [[float('inf')] * M for _ in range(N)]
    end_dist[N-1][M-1] = 0
    q = deque()
    q.append((N-1, M-1))
    
    while q:
        x, y = q.popleft()
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M:
                if end_dist[nx][ny] > end_dist[x][y] + 1:
                    end_dist[nx][ny] = end_dist[x][y] + 1
                    q.append((nx, ny))
    
    min_fatigue = float('inf')
    for A, B, C, D in magic:
        a = start_dist[A][B]
        b = end_dist[A][B]
        if a == float('inf') or b == float('inf'):
            continue
        S = a + b
        required_X = S - T
        if required_X <= 0:
            # Not possible here since S_min > T
            continue
        if C <= 1:
            continue  # C_i-1 <=0, can't contribute
        contribution = C - 1
        required_k = (required_X + (contribution - 1)) // contribution  # ceil division
        fatigue = required_k * D
        if fatigue < min_fatigue:
            min_fatigue = fatigue
    
    if min_fatigue != float('inf'):
        print(min_fatigue)
    else:
        print(-1)

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