当サイトの記事にはプロモーションが含まれています。
ABC396 - D - Minimum XOR Path
最終更新：2025-03-22 投稿日：2025-03-22
2025/03/08に行われたAtCoder Beginner Contest 396のD問題の解法についての記事です。
考えたこと
\( 2 \leq N \leq 10 \)なので、頂点\( 1 \)を固定して、\( 2 , ... , N \)に対してnext_permutationを使っても間に合いそうです。
\( N \)まで到達できれば良いので、道中で辺のラベルのXORを取りつつ、\( N \)に到達できればラベルのXORの最小値を求めていきます。
コードの例
#include <bits/stdc++.h>using namespace std;int main() {int N, M;cin >> N >> M;vector<vector<long long>> line(N + 1, vector<long long>(N + 1));vector<set<int>> lineTo(N + 1);int u, v;long long w;for (int i = 0; i < M; i++) {cin >> u >> v >> w;line.at(u).at(v) = w;line.at(v).at(u) = w;lineTo.at(u).insert(v);lineTo.at(v).insert(u);}vector<int> A(N - 1);for (int i = 0; i < N - 1; i++) {A.at(i) = i + 2;}long long ans = -1;do {long long ansNow;int pos = 1;bool flag = false;int i = 0;int nextPos;while (i < N - 1) {nextPos = A.at(i);if (lineTo.at(pos).count(nextPos)) {if (i == 0) {ansNow = line.at(pos).at(nextPos);if (nextPos == N) {flag = true;break;}}else {ansNow = ansNow xor line.at(pos).at(nextPos);if (nextPos == N) {flag = true;break;}}}else {break;}pos = nextPos;i++;}if (flag) {if (ans == -1) {ans = ansNow;}else {ans = min(ans, ansNow);}}} while (next_permutation(A.begin(), A.end()));cout << ans << endl;return 0;}
解法
次の頂点につながる辺があるかどうかはvector<set<int>> lineToで管理し、辺の重みはvector<vector<long long>> lineで管理しています。
出発点は頂点\( 1 \)に固定して、c++のnext_permutationを用いて頂点\( N \)までの辺の重みのXORを取りつつ進んでいきます。頂点\( N \)に到達できればansの更新を行い、到達できなければ次のnext_permutationで同様の処理を行います。
頂点\( 2, ... , N \)の順列は\( 9 ! == 362880\)通りなので、最大で9回辺のXORを取ることを考えても十分高速です。
これで回答となります。