結果

問題 No.3291 K-step Navigation
ユーザー srjywrdnprkt
提出日時 2025-10-09 15:25:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 338 ms / 3,000 ms
コード長 2,562 bytes
コンパイル時間 4,027 ms
コンパイル使用メモリ 293,604 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-09 15:26:05
合計ジャッジ時間 9,734 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       Kが奇数
       ->s,tを結べば1,3,5,....ステップ目に到達できるのでOK
       Kが偶数
       tがs以外の頂点と隣接しているとき、tに隣接する頂点とsを結べば2,4,...ステップ目に到達できるのでOK
       sがt以外の頂点と隣接しているとき、sに隣接する頂点とtを結べば2,4,...ステップ目に到達できるのでOK
       それ以外のとき、
       (1)s, tが孤立しているときs, tを結ばないと到達できない。しかし、この場合、1,3,5,...ステップ目でしか到達できないのでNG
       (2)s-tのグループが孤立している時、グラフに存在する奇数長の閉路の最小値をxとする。tからその閉路に辺を伸ばすと、x+3, x+5,...で到着できる。
       これは、グラフの頂点を倍加させて、奇数、偶数の状態を持たせ、奇数τ行の最短距離を求めれば良い。
    */

    ll N, M, K, s, t;
    cin >> N >> M >> K >> s >> t;
    s--; t--;
    vector<vector<ll>> E(N);
    vector con(N, vector<bool>(N));
    while(M--){
        ll u, v;
        cin >> u >> v;
        u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    auto yes=[]()->void{
        cout << "Yes" << endl;
        exit(0);
    };

    if (K % 2 == 1) yes();
    if (E[s].size() >= 1 && E[s][0] != t) yes();
    if (E[t].size() >= 1 && E[t][0] != s) yes();
    if (E[s].size() == 0 && E[t].size() == 0){
        cout << "No" << endl;
        return 0;
    }

    assert(E[s][0] == t && E[t][0] == s);
    auto min_cycle=[&](ll x)->ll{
        vector dist(N, vector<ll>(2, -1));
        queue<pair<ll, ll>> que;
        dist[x][0] = 0;
        que.push({x, 0});
        while(!que.empty()){
            auto [from, sign] = que.front();
            que.pop();
            for (auto to : E[from]){
                if (dist[to][(sign+1)%2] == -1){
                    dist[to][(sign+1)%2] = dist[from][sign]+1;
                    que.push({to, (sign+1)%2});
                }
            }
        }
        return (dist[x][1] == -1 ? (ll)9e18 : dist[x][1]);
    };
    ll mi=9e18;
    for (int i=0; i<N; i++) mi = min(mi, min_cycle(i)); 
    if (mi+3 <= K && (mi+3) % 2 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}
0