# 题目大意
给定 n 个点 m 条边的有向图，第 i 条边从结点 Ai 连向结点 Bi，权值为 Wi
求，从 1→n 的路径中（可以重复走），路径权值异或的最小值
# 数据范围
- 2≤n≤103
- 0≤m≤103
- 0 \le w_i \le 2^
# 题解
# 错解
这个错解，明显忽略了在 a1⊕...⊕an 时，并不是 a1⊕...⊕ai 越小，最终结果也越小的
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int n, m;
vector<PII> g[N];
vector<int> ans;
void dfs(int u) {
for (auto [to, val] : g[u]) {
int t = ans[u] ^ val;
if (ans[to] > t)
ans[to] = t, dfs(to);
}
}
void solve () {
cin >> n >> m, ans = vector<int>(n + 1, 1e18);
for (int i = 1, u, v, w; i <= m; i++)
cin >> u >> v >> w, g[u].push_back({v, w});
ans[1] = 0, dfs(1);
cout << (ans[n] == 1e18 ? -1 : ans[n]) << '\n';
}
|
# 正解
正解应该是，记录每个点是否遍历过这个状态（异或值，值最大不会超过 210,1024，故可以开数组来记录）
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void dfs(int u, int tmp) {
if (u == n)
res = min(res, tmp);
for (auto [to, val] : g[u]) {
int t = tmp ^ val;
if (!st[to][t])
st[to][t] = 1, dfs(to, t);
}
}
void solve () {
cin >> n >> m;
for (int i = 1, u, v, w; i <= m; i++)
cin >> u >> v >> w, g[u].push_back({v, w});
dfs(1, 0);
cout << (res == 1e18 ? -1 : res) << '\n';
}
|
