結果
問題 |
No.1190 Points
|
ユーザー |
|
提出日時 | 2024-02-18 20:20:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 277 ms / 2,000 ms |
コード長 | 1,589 bytes |
コンパイル時間 | 250 ms |
コンパイル使用メモリ | 82,916 KB |
実行使用メモリ | 108,012 KB |
最終ジャッジ日時 | 2024-09-29 00:54:37 |
合計ジャッジ時間 | 6,572 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
## https://yukicoder.me/problems/no/1190 from collections import deque def calc_dist_array(N, next_nodes, start): dist = [[-1] * N for _ in range(2)] dist[0][start] = 0 queue = deque([(start, 0)]) while len(queue) > 0: v, c = queue.popleft() for nv in next_nodes[v]: if dist[1 - c][nv] == -1: dist[1 - c][nv] = dist[c][v] + 1 queue.append((nv, 1 - c)) return dist def main(): N, M, P = map(int, input().split()) S, G = map(int, input().split()) S -= 1 G -= 1 next_nodes = [[] for _ in range(N)] for _ in range(M): u, v = map(int, input().split()) u -= 1 v -= 1 next_nodes[u].append(v) next_nodes[v].append(u) dist_array_s = calc_dist_array(N, next_nodes, S) dist_array_g = calc_dist_array(N, next_nodes, G) p = P % 2 answer_set = set() for i in range(N): for js in range(2): if dist_array_s[js][i] == -1: continue if dist_array_g[(js + p) % 2][i] == -1: continue if dist_array_s[js][i] + dist_array_g[(js + p) % 2][i] > P: continue d = dist_array_s[js][i] + dist_array_g[(js + p) % 2][i] if (P - d) % 2 == 0: answer_set.add(i + 1) answer_list = list(answer_set) answer_list.sort() if len(answer_list) == 0: print(-1) else: print(len(answer_list)) for a in answer_list: print(a) if __name__ == "__main__": main()