【AtCoder】ABC 410 D - XOR Shortest Walk | 緑コーダーが解くAtCoder

atcoder.jp

配点: 400 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1048 / NoviSteps: 1Q

問題概要
制約
考察
実装例
コメント

問題概要

$N$ 頂点 $M$ 辺の有向グラフがあり、辺 $i$ は頂点 $A_i$ から頂点 $B_i$ への重み $W_i$ の有向辺である。

頂点 $1$ から頂点 $N$ への walk のうち、walk に含まれる辺の重みのビット単位 $\mathrm{XOR}$ の最小値を求めよ。

制約

$2 \leq N \leq 1000$
$0 \leq M \leq 1000$
$0 \leq W_i \lt 2^{10}$
入力は全て整数。

考察

この問題が厄介なのは、グラフ上のサイクルを経由することで $\mathrm{XOR}$ 和が変動してしまう点にある。つまり、「今どの頂点にいるか」だけでは経路の $\mathrm{XOR}$ 和が一意に定まらないのである。

そこで、

状態 $(v, s) :=$ 現在の頂点が $v$ で、頂点 $1$ から $v$ までの $\mathrm{XOR}$ 和が $s$ である

を新たな頂点としたグラフ $G'$ を考える。

元の有向グラフ $G$ において、 $u \underset{w}{\rightarrow} v$ の重みあり有向辺が張られているとき、 $G'$ では全ての可能な $\mathrm{XOR}$ 和 $s$ に対して $(u, s) \rightarrow (v, s \oplus w)$ の重みなし有向辺が張られる。

したがって、求めるべきなのは、「 $G'$ 上で頂点 $(1, 0)$ から到達可能な頂点 $(N, s)$ について、 $s$ が最小となるようなもの」である。

これは、 $G'$ 上で BFS / DFS を行うことで求めることができる。

ここで用いたのは「頂点倍加」というテクニックで、グラフの次元を上に伸ばすことで、同じ頂点にいても異なる状態を扱うことができるというイメージ。

qiita.com

実装例

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <class T>
using Graph = vector<vector<T>>;

// ======================================== //

struct Edge
{
    int to;
    int weight;
};

int main()
{
    int N, M;
    cin >> N >> M;
    Graph<Edge> G(N);
    rep(i, 0, M)
    {
        int A, B, W;
        cin >> A >> B >> W;
        A--, B--;
        G[A].push_back({B, W});
    }

    vector<vector<bool>> visited(N, vector<bool>((1 << 10), false));
    queue<pair<int, int>> que;
    que.push({0, 0});
    visited[0][0] = true;

    while (!que.empty())
    {
        auto [now, sum] = que.front();
        que.pop();

        for (auto &&edge : G[now])
        {
            int next_v = edge.to;
            int next_sum = sum ^ edge.weight;

            if (!visited[next_v][next_sum])
            {
                visited[next_v][next_sum] = true;
                que.push({next_v, next_sum});
            }
        }
    }

    rep(bit, 0, (1 << 10))
    {
        if (visited[N - 1][bit])
        {
            cout << bit << endl;
            return 0;
        }
    }

    cout << -1 << endl;
    return 0;
}