結果

問題 No.867 避難経路
ユーザー lam6er
提出日時 2025-04-16 00:34:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,104 ms / 6,000 ms
コード長 3,246 bytes
コンパイル時間 745 ms
コンパイル使用メモリ 81,948 KB
実行使用メモリ 390,248 KB
最終ジャッジ日時 2025-04-16 00:37:01
合計ジャッジ時間 62,962 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    H = int(data[idx])
    idx += 1
    W = int(data[idx])
    idx += 1
    gx = int(data[idx]) - 1  # Convert to 0-based
    idx += 1
    gy = int(data[idx]) - 1
    idx += 1
    
    A = []
    for _ in range(H):
        row = list(map(int, data[idx:idx+W]))
        A.append(row)
        idx += W
    
    Q = int(data[idx])
    idx += 1
    queries = []
    for _ in range(Q):
        x = int(data[idx]) - 1
        y = int(data[idx+1]) - 1
        k = int(data[idx+2])
        queries.append((x, y, k))
        idx += 3
    
    # Initialize candidates for each cell
    candidates = [[[] for _ in range(W)] for _ in range(H)]
    goal_g = 1
    goal_s = A[gx][gy]
    candidates[gx][gy].append((goal_g, goal_s))
    
    # Priority queue: (priority=g+s, g, s, i, j)
    heap = []
    heapq.heappush(heap, (goal_g + goal_s, goal_g, goal_s, gx, gy))
    
    # Directions: up, down, left, right
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while heap:
        priority, g, s, i, j = heapq.heappop(heap)
        
        # Check if current (g, s) is still valid in candidates[i][j]
        current_valid = False
        for (eg, es) in candidates[i][j]:
            if eg == g and es == s:
                current_valid = True
                break
        if not current_valid:
            continue
        
        # Explore neighbors
        for dx, dy in dirs:
            ni = i + dx
            nj = j + dy
            if 0 <= ni < H and 0 <= nj < W:
                new_g = g + 1
                new_s = s + A[ni][nj]
                new_list = []
                add = True
                
                # Check existing candidates for ni, nj
                for (eg, es) in candidates[ni][nj]:
                    if eg <= new_g and es <= new_s:
                        add = False
                        break
                
                if not add:
                    continue  # New candidate is dominated
                
                # Collect non-dominated existing candidates and check if new can be added
                temp = []
                for (eg, es) in candidates[ni][nj]:
                    if not (eg >= new_g and es >= new_s):
                        temp.append((eg, es))
                
                # Check if new is dominated by any in temp
                for (eg, es) in temp:
                    if eg <= new_g and es <= new_s:
                        add = False
                        break
                
                if add:
                    temp.append((new_g, new_s))
                    # Update candidates[ni][nj]
                    candidates[ni][nj] = temp
                    # Push to heap
                    heapq.heappush(heap, (new_g + new_s, new_g, new_s, ni, nj))
    
    # Process queries
    output = []
    for x, y, k in queries:
        k_squared = k * k
        min_cost = float('inf')
        for (g, s) in candidates[x][y]:
            cost = g * k_squared + s
            if cost < min_cost:
                min_cost = cost
        output.append(str(min_cost))
    
    print('\n'.join(output))

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