結果

問題 No.3291 K-step Navigation
ユーザー shingo0909
提出日時 2025-10-03 23:19:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,382 bytes
コンパイル時間 3,062 ms
コンパイル使用メモリ 288,908 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-03 23:20:23
合計ジャッジ時間 8,162 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 TLE * 1 -- * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cstdlib>
#include <math.h>
using namespace std;

using ll = long long;
vector<int>v;
vector<bool>r;
vector<vector<int>>g;

void dfs(int f,int i,int p,int d){
    v[i]=true;
    for(int j:g[i]){
        if(j==p)continue;
        if(j==f)r[d+1]=true;
        if(v[j])continue;
        dfs(f,j,i,d+1);
    }
    v[i]=false;
    return ;
}

int main(){
    ll n,m,k,s,t;
    cin >> n >> m >> k >> s >> t;
    s--;t--;
    v.assign(n,false);
    g.resize(n);
    r.assign(n+1,false);
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        u--;v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if(k%2){
        cout << "Yes" << endl;
        return 0;
    }else{
        if((g[s].size()==0 && g[t].size()==0)){
            cout << "No" << endl;
            return 0;
        }else if((g[s].size()==1&&g[s][0]==t) 
        && (g[t].size()==1&&g[t][0]==s));
        else{
            cout << "Yes" << endl;
            return 0;
        }
    }
    for(int i=0;i<n;i++){
        dfs(i,i,-1,0);
        if(r[3])break;
    }
    int x=-1;
    for(int i=1;i<n;i+=2){
        if(r[i]){
            x=i;
            break;
        }
    }
    if(x==-1){
        cout << "No" << endl;
    }else{
        if(k>=x+3){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

    
}
0