結果

問題 No.529 帰省ラッシュ
コンテスト
ユーザー sjiki
提出日時 2024-05-04 21:57:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,094 bytes
コンパイル時間 298 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 401,264 KB
最終ジャッジ日時 2024-11-26 12:21:01
合計ジャッジ時間 44,045 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 11 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    index = 0
    n = int(data[index])
    index += 1
    m = int(data[index])
    index += 1
    
    graph = defaultdict(list)
    for _ in range(m):
        u = int(data[index]) - 1
        v = int(data[index + 1]) - 1
        graph[u].append(v)
        graph[v].append(u)
        index += 2
    
    prey = defaultdict(list)  # 各街の獲物の価値を管理するヒープ
    q = int(data[index])
    index += 1
    
    results = []
    for _ in range(q):
        query_type = int(data[index])
        if query_type == 1:
            city = int(data[index + 1]) - 1
            value = int(data[index + 2])
            heapq.heappush(prey[city], -value)  # ヒープに価値を追加（最大ヒープのため符号反転）
            index += 3
        elif query_type == 2:
            start = int(data[index + 1]) - 1
            end = int(data[index + 2]) - 1
            max_value = find_max_prey_on_path(start, end, graph, prey)
            results.append(max_value if max_value != float('-inf') else -1)  # 獲物がない場合は-1を返す
            index += 3

    # 結果を出力
    for result in results:
        print(result)

def find_max_prey_on_path(start, end, graph, prey):
    queue = deque([start])
    visited = set()
    visited.add(start)
    max_value = float('-inf')  # 最大価値を記録する変数

    while queue:
        current = queue.popleft()
        # 現在の街の獲物をチェック
        if prey[current]:
            while prey[current] and -prey[current][0] > max_value:
                max_value = -heapq.heappop(prey[current])

        if current == end:
            break  # 目的地に到達したら探索を終了

        # 隣接する街をキューに追加
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return max_value

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