結果
問題 | No.529 帰省ラッシュ |
ユーザー | sjiki |
提出日時 | 2024-05-04 21:57:47 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,094 bytes |
コンパイル時間 | 202 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 366,484 KB |
最終ジャッジ日時 | 2024-05-04 21:57:57 |
合計ジャッジ時間 | 9,205 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | TLE | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
ソースコード
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()