异或最短路径

问题描述

给定一个有向图，包含N个顶点（编号从1到N）和M条边。第i条边从顶点A_i指向顶点B_i，边权为W_i。

要求找到从顶点1到顶点N的所有路径中，路径上边权异或和的最小值。

概念说明

1. 路径(Walk)：允许重复经过顶点和边的路径
2. 异或操作：按位异或运算（相同为0，不同为1）

输入格式

第一行包含两个整数N和M，表示顶点数和边数。 接下来M行，每行三个整数A_i, B_i, W_i，描述一条有向边。

输出格式

如果不存在从1到N的路径，输出-1。 否则输出所有可能路径中边权异或和的最小值。

约束条件

• 2 ≤ N ≤ 1000
• 0 ≤ M ≤ 1000
• 1 ≤ A_i, B_i ≤ N
• 0 ≤ W_i < 2^10
• 所有输入均为整数

样例输入1

3 3
1 2 4
2 3 5
1 3 2

样例输出1

1

样例解释1

路径1→2→3的异或和为4 XOR 5 = 1，这是最小的可能值。

样例输入2

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

样例输出2

0

样例解释2

路径1→4→2→3→4的异或和为7 XOR 2 XOR 4 XOR 1 = 0。

样例输入3

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

样例输出3

-1

样例解释3

不存在从顶点1到顶点999的路径。