P5651 Basic Shortest Path Practice Problem.

YSGH is awesome.

Given a simple, undirected, connected graph $G$ with $n$ vertices and $m$ edges. Each edge has a weight. It is guaranteed that there are no multiple edges and no self-loops. Define the weight of a simple path as the XOR sum of the weights of all edges on the path. It is guaranteed that there is no simple cycle in $G$ whose edge-weight XOR sum is not $0$. There are $Q$ queries asking for the shortest simple path from $x$ to $y$.

The first line contains three positive integers $n, m, Q$. The next $m$ lines each contain three non-negative integers $x, y, v$ ($1 \le x, y \le n$), representing an undirected edge connecting $x$ and $y$ with weight $v$. It is guaranteed that there are no multiple edges and no self-loops. The next $Q$ lines each contain two positive integers $x, y$ ($1 \le x, y \le n$), representing a query.

Output $Q$ lines, each containing one integer as the answer.

| Test Point ID | $n, Q \le$ | Special Property | | :--: | :--: | :--: | | $1,2$ | $10$ | None | | $3,4$ | $20$ | None | | $5,6$ | ${10}^5$ | $m = n - 1$ | | $7,8$ | ${10}^5$ | $v \le 1$ | | $9,10$ | ${10}^5$ | None | For $100\%$ of the testdata, $1 \le n \le {10}^5$, $1 \le m \le 2n$, and $0 \le v < 2^{30}$. Translated by ChatGPT 5