結果
問題 |
No.3291 K-step Navigation
|
ユーザー |
![]() |
提出日時 | 2025-10-03 22:46:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 90 ms / 3,000 ms |
コード長 | 1,239 bytes |
コンパイル時間 | 1,895 ms |
コンパイル使用メモリ | 204,836 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-10-03 23:30:52 |
合計ジャッジ時間 | 3,891 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 51 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long int N,M,K,S,T; signed main(){ cin>>N>>M>>K>>S>>T; S--; T--; if(S > T) swap(S,T); bool flag = (K%2 == 1); bool L = false; vector<vector<int>> G(N); for(int i = 0; i < M; i++){ int a,b; cin>>a>>b; a--; b--; G[a].push_back(b); G[b].push_back(a); if(a == S && b == T) L = true; else if(a == T || b == T) flag = true; else if(a == S || b == S) flag = true; } if(flag){ cout << "Yes" << "\n"; return 0; } if(!L){ cout << "No" << "\n"; return 0; } int res = 1e18; vector<int> dist(N); for(int a = 0; a < N; a++){ vector<int> in(N); vector<int> out(N); vector<int> col(N,-1); queue<int> Q; Q.push(a); col[a] = 0; while(!Q.empty()){ int now = Q.front(); Q.pop(); for(int i:G[now]){ //cout << a << " " << i << " " << now << " " << col[a] << " " << col[i] << " " << col[now] << "\n"; if(col[i] == -1){ col[i] = 1 - col[now]; in[i] = in[now] + 1; Q.push(i); } else{ if(col[i] == col[now]){ res = min(res,in[i] + in[now] + 1); } } } } } int ans = res; 3+ans <= K ? cout << "Yes" << "\n" : cout << "No" << "\n"; }