結果
問題 |
No.1190 Points
|
ユーザー |
![]() |
提出日時 | 2023-06-22 05:46:13 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 198 ms / 2,000 ms |
コード長 | 2,285 bytes |
コンパイル時間 | 4,519 ms |
コンパイル使用メモリ | 143,400 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-06-29 13:41:09 |
合計ジャッジ時間 | 8,647 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; struct Node { int v; int dist; Node(int v = -1, int dist = -1) { this->v = v; this->dist = dist; } bool operator>(const Node &n) const { return dist > n.dist; } }; int main() { int N, M, P; cin >> N >> M >> P; int S, G; cin >> S >> G; vector<int> E[N + 1]; for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; E[u].push_back(v); E[v].push_back(u); } int min_distance[2][N + 1][2]; memset(min_distance, -1, sizeof(min_distance)); for (int i = 0; i < 2; ++i) { int root = (i == 0) ? S : G; queue<Node> que; que.push(Node(root, 0)); bool visited[N + 1][2]; memset(visited, false, sizeof(visited)); while (not que.empty()) { Node node = que.front(); que.pop(); int t = node.dist % 2; if (visited[node.v][t]) continue; visited[node.v][t] = true; min_distance[i][node.v][t] = node.dist; for (int u : E[node.v]) { que.push(Node(u, node.dist + 1)); } } } vector<int> ans; for (int v = 1; v <= N; ++v) { int d1 = INT_MAX; int d2 = INT_MAX; if (P % 2 == 0) { if (min_distance[0][v][0] != -1 && min_distance[1][v][0] != -1) { d1 = min_distance[0][v][0] + min_distance[1][v][0]; } if (min_distance[0][v][1] != -1 && min_distance[1][v][1] != -1) { d2 = min_distance[0][v][1] + min_distance[1][v][1]; } } else { if (min_distance[0][v][0] != -1 && min_distance[1][v][1] != -1) { d1 = min_distance[0][v][0] + min_distance[1][v][1]; } if (min_distance[0][v][1] != -1 && min_distance[1][v][0] != -1) { d2 = min_distance[0][v][1] + min_distance[1][v][0]; } } // fprintf(stderr, "v: %d, d1: %d, d2: %d\n", v, d1, d2); if ((d1 <= P && (P - d1) % 2 == 0) || (d2 <= P && (P - d2) % 2 == 0)) { ans.push_back(v); } } if (ans.empty()) { cout << -1 << endl; } else { cout << ans.size() << endl; for (int v : ans) { cout << v << endl; } } return 0; }