結果
問題 |
No.1190 Points
|
ユーザー |
![]() |
提出日時 | 2025-08-23 22:54:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 397 ms / 2,000 ms |
コード長 | 1,234 bytes |
コンパイル時間 | 368 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 122,640 KB |
最終ジャッジ日時 | 2025-08-23 22:54:42 |
合計ジャッジ時間 | 9,320 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
N,M,P = map(int,input().split()) S,G = map(int,input().split()) S -= 1 G -= 1 UV = [list(map(int,input().split())) for _ in range(M)] E = [[] for _ in range(N)] for u, v in UV: u -= 1 v -= 1 E[u].append(v) E[v].append(u) INF = 10 ** 16 vtd1 = [[INF,INF] for _ in range(N)] vtd1[S][0] = 0 Q = [S] Q2 = [] i = 0 while i < P and Q: i += 1 while Q: x = Q.pop() for y in E[x]: if vtd1[y][i%2] == INF: vtd1[y][i%2] = i Q2.append(y) Q,Q2 = Q2,Q vtd2 = [[INF,INF] for _ in range(N)] vtd2[G][0] = 0 Q = [G] Q2 = [] i = 0 while i < P and Q: i += 1 while Q: x = Q.pop() for y in E[x]: if vtd2[y][i%2] == INF: vtd2[y][i%2] = i Q2.append(y) Q,Q2 = Q2,Q if vtd1[G][P%2] == INF: print(-1) exit() ans = [] for i in range(N): if P % 2 == 0: if vtd1[i][0] + vtd2[i][0] <= P: ans.append(i+1) elif vtd1[i][1] + vtd2[i][1] <= P: ans.append(i+1) else: if vtd1[i][0] + vtd2[i][1] <= P: ans.append(i+1) elif vtd1[i][1] + vtd2[i][0] <= P: ans.append(i+1) print(len(ans)) for a in ans: print(a)