結果

問題 No.2366 登校
ユーザー lam6er
提出日時 2025-03-20 18:53:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,545 bytes
コンパイル時間 227 ms
コンパイル使用メモリ 81,908 KB
実行使用メモリ 79,400 KB
最終ジャッジ日時 2025-03-20 18:54:21
合計ジャッジ時間 2,619 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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_val = int(input[ptr]); ptr += 1

    magical = []
    for _ in range(K):
        A = int(input[ptr])-1; ptr += 1
        B = int(input[ptr])-1; ptr += 1
        C = int(input[ptr]); ptr += 1
        D = int(input[ptr]); ptr += 1
        magical.append((A, B, C, D))

    # BFS for d_start (from (0,0))
    d_start = [[-1]*M for _ in range(N)]
    q = deque()
    q.append((0, 0))
    d_start[0][0] = 0
    while q:
        i, j = q.popleft()
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            ni, nj = i+dx, j+dy
            if 0 <= ni < N and 0 <= nj < M and d_start[ni][nj] == -1:
                d_start[ni][nj] = d_start[i][j] + 1
                q.append((ni, nj))

    # BFS for d_goal (from (N-1, M-1))
    d_goal = [[-1]*M for _ in range(N)]
    q = deque()
    q.append((N-1, M-1))
    d_goal[N-1][M-1] = 0
    while q:
        i, j = q.popleft()
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            ni, nj = i+dx, j+dy
            if 0 <= ni < N and 0 <= nj < M and d_goal[ni][nj] == -1:
                d_goal[ni][nj] = d_goal[i][j] + 1
                q.append((ni, nj))

    # Check if goal is reachable
    S = d_start[N-1][M-1]
    if S == -1:
        print(-1)
        return

    # Case 1: Direct path is possible
    if S <= T_val:
        print(0)
        return

    # Check if any magical cell provides a path within T without using magic
    valid_path_found = False
    for A, B, C, D in magical:
        if d_start[A][B] != -1 and d_goal[A][B] != -1:
            s_i = d_start[A][B] + d_goal[A][B]
            if s_i <= T_val:
                valid_path_found = True
                break
    if valid_path_found:
        print(0)
        return

    # Calculate minimum fatigue using magical cells
    min_fatigue = float('inf')
    for A, B, C, D in magical:
        ds = d_start[A][B]
        dg = d_goal[A][B]
        if ds == -1 or dg == -1:
            continue
        s_i = ds + dg
        R = s_i - T_val
        if R <= 0:
            continue
        if C == 1:
            continue  # No time reduction
        reduce_per = C - 1
        m = (R + reduce_per - 1) // reduce_per
        fatigue = m * D
        if fatigue < min_fatigue:
            min_fatigue = fatigue

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

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