結果
問題 |
No.92 逃走経路
|
ユーザー |
![]() |
提出日時 | 2025-09-21 22:38:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,619 ms / 5,000 ms |
コード長 | 818 bytes |
コンパイル時間 | 420 ms |
コンパイル使用メモリ | 82,412 KB |
実行使用メモリ | 76,988 KB |
最終ジャッジ日時 | 2025-09-21 22:38:57 |
合計ジャッジ時間 | 9,669 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
from collections import defaultdict N, M, K = map(int, input().split()) cost = [defaultdict(list) for _ in range(N)] for i in range(M): a, b, c = map(int, input().split()) a -= 1 b -= 1 cost[a][c].append(b) cost[b][c].append(a) D = list(map(int, input().split())) ans = set() for i in range(N): # 出発点 positions = {i} next_positions = set() for j in range(K): for pos in positions: # pos から D[j] のコストで行ける場所 for nex in cost[pos][D[j]]: next_positions.add(nex) positions = next_positions next_positions = set() # K回の移動後になお、positionsにいる頂点が答え for pos in positions: ans.add(pos + 1) ans2 = sorted(ans) print(len(ans2)) print(*ans2)