結果
問題 |
No.1190 Points
|
ユーザー |
![]() |
提出日時 | 2020-08-22 14:34:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 1,593 bytes |
コンパイル時間 | 4,238 ms |
コンパイル使用メモリ | 259,196 KB |
最終ジャッジ日時 | 2025-01-13 08:46:32 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/extc++.h> #ifndef DUMP #define DUMP(...) (void)0 #endif using namespace std; struct graph { struct edge { int src, dst; int operator-(int v) const { return src ^ dst ^ v; } }; int n, m; vector<edge> edges; vector<vector<pair<int, int>>> adj; graph(int _n = 0) : n(_n), m(0), adj(n) {} int add(const edge& e, bool directed = false) { edges.push_back(e); adj[e.src].emplace_back(m, e.dst); if (not directed) adj[e.dst].emplace_back(m, e.src); return m++; } }; vector<int> bfs(const graph& g, int s) { vector d(g.n, 0x3f3f3f3f); queue<int> que; d[s] = 0; que.push(s); while (not empty(que)) { int v = que.front(); que.pop(); for (auto [id, u] : g.adj[v]) if (d[u] == 0x3f3f3f3f) { d[u] = d[v] + 1; que.push(u); } } return d; } int main() { cin.tie(nullptr)->sync_with_stdio(false); int n, m, p; cin >> n >> m >> p; int s, t; cin >> s >> t; --s, --t; graph g(n * 2); while (m--) { int u, v; cin >> u >> v; --u, --v; g.add({u * 2, v * 2 + 1}); g.add({u * 2 + 1, v * 2}); } auto ds = bfs(g, s * 2); if (ds[t * 2 + (p & 1)] > p) { cout << "-1\n"; exit(0); } auto dt = bfs(g, t * 2); vector<int> res; for (int v = 0; v < n; ++v) { for (int x : {0, 1}) { if (ds[v * 2 + x] + dt[v * 2 + ((p & 1) ^ x)] <= p) { res.push_back(v); break; } } } cout << size(res) << '\n'; for (auto&& e : res) cout << e + 1 << '\n'; }