結果
問題 |
No.1190 Points
|
ユーザー |
|
提出日時 | 2025-05-26 05:03:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 7,844 bytes |
コンパイル時間 | 4,443 ms |
コンパイル使用メモリ | 316,700 KB |
実行使用メモリ | 20,488 KB |
最終ジャッジ日時 | 2025-05-26 05:03:57 |
合計ジャッジ時間 | 8,612 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
// competitive-verifier: PROBLEM #include <iostream> #include <vector> /** * @brief 重み付きグラフ * * @tparam T 辺の重みの型 */ template <class T> struct Graph { private: struct _edge { constexpr _edge() : _from(), _to(), _weight() {} constexpr _edge(int from, int to, T weight) : _from(from), _to(to), _weight(weight) {} constexpr bool operator<(const _edge &rhs) const { return weight() < rhs.weight(); } constexpr bool operator>(const _edge &rhs) const { return rhs < *this; } constexpr int from() const { return _from; } constexpr int to() const { return _to; } constexpr T weight() const { return _weight; } private: int _from, _to; T _weight; }; public: using edge_type = typename Graph<T>::_edge; Graph() : _size(), edges() {} Graph(int v) : _size(v), edges(v) {} const auto &operator[](int i) const { return edges[i]; } auto &operator[](int i) { return edges[i]; } const auto begin() const { return edges.begin(); } auto begin() { return edges.begin(); } const auto end() const { return edges.end(); } auto end() { return edges.end(); } constexpr int size() const { return _size; } void add_edge(const edge_type &e) { edges[e.from()].emplace_back(e); } void add_edge(int from, int to, T weight = T(1)) { edges[from].emplace_back(from, to, weight); } void add_edges(int from, int to, T weight = T(1)) { edges[from].emplace_back(from, to, weight); edges[to].emplace_back(to, from, weight); } void input_edge(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; T weight; std::cin >> from >> to >> weight; add_edge(from - base, to - base, weight); } } void input_edges(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; T weight; std::cin >> from >> to >> weight; add_edges(from - base, to - base, weight); } } private: int _size; std::vector<std::vector<edge_type>> edges; }; template <> struct Graph<void> { private: struct _edge { constexpr _edge() : _from(), _to() {} constexpr _edge(int from, int to) : _from(from), _to(to) {} constexpr int from() const { return _from; } constexpr int to() const { return _to; } constexpr int weight() const { return 1; } constexpr bool operator<(const _edge &rhs) const { return weight() < rhs.weight(); } constexpr bool operator>(const _edge &rhs) const { return rhs < *this; } private: int _from, _to; }; public: using edge_type = typename Graph<void>::_edge; Graph() : _size(), edges() {} Graph(int v) : _size(v), edges(v) {} const auto &operator[](int i) const { return edges[i]; } auto &operator[](int i) { return edges[i]; } const auto begin() const { return edges.begin(); } auto begin() { return edges.begin(); } const auto end() const { return edges.end(); } auto end() { return edges.end(); } constexpr int size() const { return _size; } void add_edge(const edge_type &e) { edges[e.from()].emplace_back(e); } void add_edge(int from, int to) { edges[from].emplace_back(from, to); } void add_edges(int from, int to) { edges[from].emplace_back(from, to); edges[to].emplace_back(to, from); } void input_edge(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; std::cin >> from >> to; add_edge(from - base, to - base); } } void input_edges(int m, int base = 1) { for (int i = 0; i < m; ++i) { int from, to; std::cin >> from >> to; add_edges(from - base, to - base); } } private: int _size; std::vector<std::vector<edge_type>> edges; }; #ifdef ATCODER #pragma GCC target("sse4.2,avx512f,avx512dq,avx512ifma,avx512cd,avx512bw,avx512vl,bmi2") #endif #pragma GCC optimize("Ofast,fast-math,unroll-all-loops") #include <bits/stdc++.h> #ifndef ATCODER #pragma GCC target("sse4.2,avx2,bmi2") #endif template <class T, class U> constexpr bool chmax(T &a, const U &b) { return a < (T)b ? a = (T)b, true : false; } template <class T, class U> constexpr bool chmin(T &a, const U &b) { return (T)b < a ? a = (T)b, true : false; } constexpr std::int64_t INF = 1000000000000000003; constexpr int Inf = 1000000003; constexpr double EPS = 1e-7; constexpr double PI = 3.14159265358979323846; #define FOR(i, m, n) for (int i = (m); i < int(n); ++i) #define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i) #define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i) #define rep(i, n) FOR (i, 0, n) #define repn(i, n) FOR (i, 1, n + 1) #define repr(i, n) FORR (i, n, 0) #define repnr(i, n) FORR (i, n + 1, 1) #define all(s) (s).begin(), (s).end() struct Sonic { Sonic() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(20); } constexpr void operator()() const {} } sonic; using namespace std; using ll = std::int64_t; using ld = long double; template <class T, class U> std::istream &operator>>(std::istream &is, std::pair<T, U> &p) { return is >> p.first >> p.second; } template <class T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &i : v) is >> i; return is; } template <class T, class U> std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) { return os << '(' << p.first << ',' << p.second << ')'; } template <class T> std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) { for (auto it = v.begin(); it != v.end(); ++it) os << (it == v.begin() ? "" : " ") << *it; return os; } template <class Head, class... Tail> void co(Head &&head, Tail &&...tail) { if constexpr (sizeof...(tail) == 0) std::cout << head << '\n'; else std::cout << head << ' ', co(std::forward<Tail>(tail)...); } template <class Head, class... Tail> void ce(Head &&head, Tail &&...tail) { if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n'; else std::cerr << head << ' ', ce(std::forward<Tail>(tail)...); } void Yes(bool is_correct = true) { std::cout << (is_correct ? "Yes\n" : "No\n"); } void No(bool is_not_correct = true) { Yes(!is_not_correct); } void YES(bool is_correct = true) { std::cout << (is_correct ? "YES\n" : "NO\n"); } void NO(bool is_not_correct = true) { YES(!is_not_correct); } void Takahashi(bool is_correct = true) { std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n'; } void Aoki(bool is_not_correct = true) { Takahashi(!is_not_correct); } auto f(const Graph<void> &g, int s) { int n = g.size(); vector dp(n, vector(2, Inf)); queue<pair<int, int>> que; dp[s][0] = 0; que.emplace(s, 0); while (!que.empty()) { auto [x, y] = que.front(); que.pop(); for (auto e : g[x]) { if (chmin(dp[e.to()][!y], dp[x][y] + 1)) que.emplace(e.to(), !y); } } return dp; } int main(void) { int n, m, p; cin >> n >> m >> p; int s, g; cin >> s >> g; --s, --g; Graph<void> graph(n); graph.input_edges(m); auto dps = f(graph, s); auto dpg = f(graph, g); vector<int> ans; if (p & 1) { rep (i, n) { if (min(dps[i][0] + dpg[i][1], dps[i][1] + dpg[i][0]) <= p) ans.emplace_back(i + 1); } } else { rep (i, n) { if (min(dps[i][0] + dpg[i][0], dps[i][1] + dpg[i][1]) <= p) ans.emplace_back(i + 1); } } if (ans.empty()) { co(-1); } else { co(ans.size()); for (auto e : ans) co(e); } return 0; }