結果
問題 | No.2674 k-Walk on Bipartite |
ユーザー |
|
提出日時 | 2024-03-15 22:24:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 1,585 bytes |
コンパイル時間 | 2,232 ms |
コンパイル使用メモリ | 203,100 KB |
最終ジャッジ日時 | 2025-02-20 05:30:08 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<class T> istream& operator >> (istream& is, vector<T>& vec) {for(T& x : vec) is >> x;return is;}template<class T> ostream& operator << (ostream& os, const vector<T>& vec) {if(vec.empty()) return os;os << vec[0];for(auto it = vec.begin(); ++it != vec.end(); ) os << ' ' << *it;return os;}int main(){ios::sync_with_stdio(false);cin.tie(0);int n, m, s, t, k;cin >> n >> m >> s >> t >> k;s--, t--;vector<vector<int>> g(n);queue<int> que;vector<int> dp(n, 1 << 30);for(int i = 0; i < m; i++){int u, v;cin >> u >> v;u--, v--;g[u].emplace_back(v);g[v].emplace_back(u);}que.emplace(s);dp[s] = 0;while(!que.empty()){int v = que.front();que.pop();for(auto &&u : g[v]){if(dp[v] + 1 >= dp[u]) continue;dp[u] = dp[v] + 1;que.emplace(u);}}if(n == 1){cout << "No\n";return 0;}if(dp[t] == (1 << 30)){if(n == 2){cout << (k % 2 == (s != t) ? "Unknown" : "No") << '\n';return 0;}cout << "Unknown" << '\n';return 0;}if(abs(dp[t] - k) & 1){cout << "No\n";return 0;}assert(k >= 1);if(s == t){int cnt = n - count(dp.begin(), dp.end(), 1 << 30);cout << (cnt > 1 ? "Yes" : "Unknown") << '\n';return 0;}cout << (dp[t] <= k ? "Yes" : "Unknown") << '\n';}