【ABC410 D問題】考察から実装(c++)まで

Last updated at 2025-06-17Posted at 2025-06-17

AtCoderBeginnerContest410の解説＆感想です。
コンテストリンク

問題一覧

D問題 - XOR Shortest Walk

問題概要

$N$頂点$M$辺の重み($W_i$)つき有向グラフがある。頂点$1$から$N$へ向かうwalkのうち、walkに含まれる辺の重みのビット単位$XOR$の最小値を求めよ。
(walkとは、頂点$1$から$N$までの経路で、同じ頂点や辺を複数回通ってもいいもの)

制約

$2 \le N \le 1000$
$0 \le M \le 1000$
$0 \le W \le 2^10$

考察

「ビット単位$XOR$なのでビットごとに考えましょう」をして時間をかなり溶かしてしまった...。厳しい。改めて制約を眺めると$W \le 2^{10}$が怪しい気がする。単純な探索で行けるなら$10^9$なり$2^{60}$なりでいいはず。おそらく$O(N \times max(W))$とかになるだろうな〜（メタ読み）。

ここで「拡張ダイクストラ」を履修していれば、同じようなことをすればいいと気づく。「各頂点」と「そこに来たときのXOR(W)の状態（001とか110とか）」を全探索すればいい。
拡張ダイクストラを知らなくてもbitDPを履修していたら思いつけそう。
計算量は、各頂点の全探索が$O(N+M)$で、それぞれの頂点にXOR(W)の状態のパターンが$2^{10}$なので、全体で$O((N+M)*max(W))$。

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll,ll>;
using vvpll = vector<vector<pair<ll,ll>>>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;

int main(){
    //入力
    ll N,M;
    cin>>N>>M;
    
    vvpll nexts(N);
    for(int i=0;i<M;i++){
        ll a,b,w;
        cin>>a>>b>>w;
        nexts[a-1].push_back({w, b-1});
    }
    
    //頂点1でXOR:0の状態からたどり着けるかどうか
    vvb canReach(N, vb(1024,false));
    canReach[0][0] = true;
    
    function<void(ll,ll)> dfs = [&](ll i, ll w){
        //頂点iから行ける頂点たちを全探索
        for(pll next: nexts[i]){
            ll nw = next.first ^ w;
            ll ni = next.second;
            
            //すでにたどり着けることがわかってれば無視
            if(canReach[ni][nw]) continue;
            
            canReach[ni][nw] = true;
            dfs(ni, nw);
        }
    };
    dfs(0,0);
    
    //頂点N-1のたどり着けるwの中で、いちばん小さいものを表示
    for(int w=0;w < 1024;w++){
        if(canReach[N-1][w]){
            cout<<w<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
}

その他問題

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up