#1056732 (PyPy3) No.2366 登校

• 問題: No.2366 登校
• ユーザー: lam6er
• 提出日時: 2025-03-20 21:17:14
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 2,545 bytes
• コンパイル時間: 347 ms
• コンパイル使用メモリ: 82,824 KB
• 実行使用メモリ: 79,524 KB
• 最終ジャッジ日時: 2025-03-20 21:18:16
• 合計ジャッジ時間: 2,532 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 2
other	AC * 22 WA * 3

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX