結果

問題 No.2366 登校
ユーザー gew1fw
提出日時 2025-06-12 18:16:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,925 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 129,292 KB
最終ジャッジ日時 2025-06-12 18:16:43
合計ジャッジ時間 7,496 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 WA * 11 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

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_val = int(input[idx]); idx +=1

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

    # Compute minimal steps from (0,0) to (N-1, M-1)
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]
    def bfs(start_x, start_y, target_x, target_y):
        visited = [[-1 for _ in range(M)] for __ in range(N)]
        q = deque()
        q.append((start_x, start_y))
        visited[start_x][start_y] = 0
        while q:
            x, y = q.popleft()
            if x == target_x and y == target_y:
                return visited[x][y]
            for dx, dy in dirs:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == -1:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))
        return -1  # unreachable

    S = bfs(0, 0, N-1, M-1)
    if S == -1:
        print(-1)
        return

    if S <= T_val:
        print(0)
        return

    # Need to use time rewinds. Check if any mysterious square is on any path.
    min_D = None
    for (A, B, D) in mysterious:
        # Check if (A,B) is reachable from start
        steps1 = bfs(0, 0, A, B)
        if steps1 == -1:
            continue
        # Check if end is reachable from (A,B)
        steps2 = bfs(A, B, N-1, M-1)
        if steps2 == -1:
            continue
        if min_D is None or D < min_D:
            min_D = D

    if min_D is None:
        print(-1)
    else:
        k = S - T_val
        print(k * min_D)

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