ABC410 D - XOR Shortest Walk

D - XOR Shortest Walk

问题陈述

有一个有向图，包含 $N$ 个顶点和 $M$ 条边，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。

第 $i$ 条边是从顶点 $A_i$ 到顶点 $B_i$ 的有向边，权重为 $W_i$。

请找到一条从顶点 $1$ 到顶点 $N$ 的路径，使得路径上边权重的按位异或（XOR）值最小。

约束条件

• $2 \leq N \leq 1000$
• $0 \leq M \leq 1000$
• $1 \leq A_i, B_i \leq N$
• $0 \leq W_i < 2^{10}$

所有输入值均为整数。

输入格式

N M
A_1 B_1 W_1
A_2 B_2 W_2
⋮
A_M B_M W_M

输出格式

• 如果不存在从顶点 $1$ 到顶点 $N$ 的路径，输出 -1。
• 如果存在，输出路径上边权重异或值的最小值。

输入输出样例

示例 1

3 3
1 2 4
2 3 5
1 3 2

1

路径 (边 1, 边 2) 的边权异或值是 $1$。

示例 2

4 4
1 4 7
4 2 2
2 3 4
3 4 1

0

路径 (边 1, 边 2, 边 3, 边 4) 的异或值是 $0$。

示例 3

999 4
1 2 9
2 1 8
1 2 7
1 1 6

-1

不存在从顶点 $1$ 到顶点 $999$ 的路径，输出 $-1$。

---

解析

很标准的一道DFS/BFS题目，不过这里因为存在一个异或，所以存在一个巧思。我们将访问过的标记数组改为二维的，这样一来，我们不会漏掉更优答案的同时避免了环。

示例代码

DFS做法

vector<PII> G[N];
int n, m, ans = inf;
bool vis[N][M];

void dfs(int u, int x)
{
    if (vis[u][x]) return;
    vis[u][x] = true;

    if (u == n)
    {
        ans = min(ans, x);
    }
    for (auto ed : G[u]) dfs(ed.first, x ^ ed.second);
}

void solve()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back({v, w});
    }
    dfs(1, 0);
    cout << (ans == inf ? -1 : ans) << endl;
}

BFS做法

vector<PII> G[N];
int n, m;
bool vis[N][M];
queue<PII> q;

void solve()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back({v, w});
    }
    q.push({1, 0}); vis[1][0] = 1;
    while (q.size())
    {
        auto [u, val] = q.front(); q.pop();
        for (auto [v, w] : G[u])
        {
            if (!vis[v][val ^ w])
            {
                vis[v][val ^ w] = 1;
                q.push({v, val ^ w});
            }
        }
    }
    int ans = -1;
    for (int i = 0; i < 1024; i++) if (vis[n][i]) {ans = i; break;};
    cout << ans << endl;
}