D - Minimum XOR Path
Source: atcoder
Difficulty: 400

Problem Statement
You are given a simple connected undirected graph with
N
vertices numbered
1
through
N
and
M
edges numbered
1
through
M
. Edge
i
connects vertices
u_i
and
v_i
, and has a label
w_i
.
Among all simple paths (paths that do not pass through the same vertex more than once) from vertex
1
to vertex
N
, find the minimum XOR of the labels of the edges on the path.
Notes on XOR
For non-negative integers
A
and
B
, their XOR
A \oplus B
is defined as follows:
In the binary representation of
A \oplus B
, the digit in the place corresponding to
2^k \,(k \ge 0)
is
1
if and only if exactly one of the digits in the same place of
A
and
B
is
1
; otherwise, it is
0
.
For example,
3 \oplus 5 = 6
(in binary:
011 \oplus 101 = 110
).
In general, the XOR of
k
integers
p_1, \dots, p_k
is defined as
(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)
. It can be proved that it does not depend on the order of
p_1, \dots, p_k
.
Constraints
2 \leq N \leq 10
N-1 \leq M \leq \frac{N(N-1)}{2}
1 \leq u_i < v_i \leq N
0 \leq w_i < 2^{60}
The given graph is a simple connected undirected graph.
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
M
u_1
v_1
w_1
u_2
v_2
w_2
\vdots
u_M
v_M
w_M
Output
Print the answer.
Sample Input 1
4 4
1 2 3
2 4 5
1 3 4
3 4 7
Sample Output 1
3
There are two simple paths from vertex
1
to vertex
4
:
1 \to 2 \to 4
1 \to 3 \to 4
The XOR of the labels on the edges of the first path is
6
, and that of the second path is
3
. Therefore, the answer is
3
.
Sample Input 2
4 3
1 2 1
2 3 2
3 4 4
Sample Output 2
7
Sample Input 3
7 10
1 2 726259430069220777
1 4 988687862609183408
1 5 298079271598409137
1 6 920499328385871537
1 7 763940148194103497
2 4 382710956291350101
3 4 770341659133285654
3 5 422036395078103425
3 6 472678770470637382
5 7 938201660808593198
Sample Output 3
186751192333709144

C++ solution:
// Problem: D - Minimum XOR Path
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// Problem: F. Trulimero Trulicina
// Contest: Codeforces - Codeforces Round 1017 (Div. 4)
// URL: https://codeforces.com/contest/2094/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

//宏定义----------------------------------
#define bg(x) begin(x)
#define rall(x) rbegin(x), rend(x) 
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define pb push_back
#define eb emplace_back


using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;

template<typename T> using vc=vector<T>;
using vi=vc<int>;
using vll=vc<ll>;
using vpi=vc<pii>;
using vpll=vc<pll>;
using vvi=vc<vi>;
using vvll=vc<vll>;

template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
template<class T> using pq = priority_queue<T>;

#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(const vector<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
template<class T> int upb(const vector<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }

#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(a)-1; i>=(b); --i)
#define each(x,a) for (auto& x: a)

#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

template<class T> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0;
}

template<class T> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0;
}
constexpr int pct(int x) { return __builtin_popcount(x); }  
constexpr int bits(int x) {  // assert(x >= 0); 
	return x == 0 ? 0 : 31 - __builtin_clz(x);
}  // floor(log2(x))
constexpr int p2(int x) { return 1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }

template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}

const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1};
const ll inf= 1LL << 60;
const int P=1e9+7;
const int N=2e5+5;
const int mod=998244353;
//宏定义----------------------------------





void solve(){
	int n, m;
	cin >> n >> m;
	vector<vector<array<ll, 2>>> adj(n);
	rep(i, 0, m){
		int u, v;
		ll w;
		cin >> u >> v >> w;
		u--, v--;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}
	vll f(n, inf), vis(n);
	f[0] = 0;
	auto dfs = [&](auto&& self, int s,ll v)->void{
		
		if(s == n - 1){
			return;
		}
		vis[s] = 1;
		for(auto [x, w] : adj[s]){
			if(vis[x]) continue;
			// cout << s << " " << x << "\n";
			f[x] = min(f[x], v ^ w);
			self(self, x, v ^ w);
		}
		vis[s] = 0;
	};
	dfs(dfs, 0, 0);
	cout << f[n - 1] ;
	
}




int32_t main(){
	// cout.precision(10); cout.setf(ios::fixed);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;
	// cin>>T;
	while(T--){
		solve();
	}
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"runtime"
	"sort"
	"strconv"
	"strings"
)

var scanner = bufio.NewScanner(os.Stdin)
var wtr = bufio.NewWriter(os.Stdout)

type pair struct {
	uv int
	w  int
}

func main() {
	defer flush()

	n, m := int2()
	uvw := make([][]pair, n)
	for i := 0; i < m; i++ {
		u, v, w := int3()
		u--
		v--
		uvw[u] = append(uvw[u], pair{v, w})
		uvw[v] = append(uvw[v], pair{u, w})
	}

	visited := make([]bool, n)
	ans := 1 << 60
	var dfs func(v int, x int)
	dfs = func(v int, x int) {
		if v == n-1 {
			ans = min(ans, x)
			return
		}
		visited[v] = true
		for _, pair := range uvw[v] {
			if visited[pair.uv] {
				continue
			}
			dfs(pair.uv, x^pair.w)
		}
		visited[v] = false
	}

	dfs(0, 0)

	print(ans)
}

// var dfs func(v int, p int64)
// // v 今の頂点, p 比較に使う数値
// dfs = func(v int, p int64) {
// 	if used[v] {
// 		return
// 	}
// 	used[v] = true
// 	// 今の頂点に隣接してる頂点を調べる
// 	for _, e := range edges[v] {
// 		// 隣接頂点が調査済み
// 		if used[e.to] {
// 			continue
// 		}
// 		print("x", x)
// 		print("e", e)
// 		print("v", v)
// 		// 次の頂点の値は 今の頂点+今の重さ
// 		print(e.to, x[v], e.wait)
// 		x[e.to] = x[v] + int64(e.wait)
// 		dfs(e.to, int64(v))
// 	}
// }

// for i := 0; i < n; i++ {
// 	if used[i] {
// 		continue
// 	}
// 	// 全頂点に対して調べる
// 	dfs(i, int64(0))
// }

// --- init

const baseRune = 'a'

func init() {
	scanner.Buffer([]byte{}, math.MaxInt64)
	scanner.Split(bufio.ScanWords)
}

func int1() int {
	scanner.Scan()
	i, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func str() string {
	scanner.Scan()
	return scanner.Text()
}

func strs(len int) []string {

	inputs := make([]string, len)
	for i := 0; i < len; i++ {
		scanner.Scan()
		inputs[i] = scanner.Text()
	}
	return inputs
}

func ints(len int) []int {

	inputs := make([]int, len)
	for i := 0; i < len; i++ {
		scanner.Scan()
		inputStr := scanner.Text()
		input, err := strconv.Atoi(inputStr)
		if err != nil {
			panic(err)
		}
		inputs[i] = input
	}

	return inputs
}

func int2() (int, int) {
	ints := ints(2)
	return ints[0], ints[1]
}

func int3() (int, int, int) {
	ints := ints(3)
	return ints[0], ints[1], ints[2]
}

func int64_() int64 {
	i, err := strconv.ParseInt(str(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}

func toSlice[T comparable](t ...T) []T {
	list := make([]T, 0, len(t))
	return append(list, t...)
}

// 左から探す二分探索 binary search
func bisectLeft(list []int, target int) int {
	return sort.SearchInts(list, target)
}

// 右から探す二分探索 binary search
func bisectRight(list []int, target int) int {
	return sort.Search(len(list), func(i int) bool { return list[i] > target })
}

// 独自定義の二分探索 binary search
func bisect(list []int, target int) int {
	low := 0
	high := len(list) - 1

	for low <= high {

		mid := (low + high) / 2

		if list[mid] == target {
			return mid
		}
		if list[mid] < target {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return -1
}

// 文字列をアルファベット順のインデックスに変換して数値配列で読み取る
func readStrAsIndex() []int {
	scanner.Scan()
	s := scanner.Text()
	return sToIndex(s, baseRune)
}

// 文字列を基準文字に対する相対的な整数配列に変換
func sToIndex(s string, baseRune rune) []int {
	r := make([]int, len(s))
	for i, v := range s {
		r[i] = int(v - baseRune)
	}
	return r
}

func sortDesc(ints []int) {
	sort.Sort(sort.Reverse(sort.IntSlice(ints)))
}

func sortAsc(ints []int) {
	sort.Ints(ints)
}

func reverseString(s string) string {
	rs := []rune(s)
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		rs[i], rs[j] = rs[j], rs[i]
	}
	return string(rs)
}

func iToS(i int) string {
	return strconv.Itoa(i)
}

func i64ToS(i int64) string {
	return strconv.FormatInt(i, 10)
}

func sToI(s string) int {
	i, err := strconv.Atoi(s)
	if err != nil {
		panic(err)
	}
	return i
}

func maxlist(a []int, max int) int {
	for _, v := range a {
		if v > max {
			max = v
		}
	}
	return max
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func maxu(a, b uint64) uint64 {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func min64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func makeMap[T comparable](list []T) map[T]struct{} {
	m := make(map[T]struct{}, len(list))
	for _, v := range list {
		m[v] = struct{}{}
	}
	return m
}

type Queue struct {
	data [][2]int
	size int
}

func NewQueue(len int) *Queue {
	return &Queue{
		data: make([][2]int, len, 0),
		size: 0,
	}
}

// キューにデータを追加する
func (q *Queue) Push(i [2]int) {
	q.data = append(q.data, i)
	q.size++
}

// キューの最新データを削除
func (q *Queue) Pop() bool {
	if q.IsEmpty() {
		return false
	}
	q.size--
	q.data = q.data[1:]
	return true
}

// キューの最新データを取得
func (q *Queue) Front() [2]int {
	return q.data[0]
}

func (q *Queue) IsEmpty() bool {
	return q.size == 0
}

func (q *Queue) String() string {
	return fmt.Sprint(q.data)
}

// ユークリッド距離
func euclidean(x1, x2, y1, y2 int) float64 {
	return math.Sqrt(math.Pow(float64(x1-x2), 2) + math.Pow(float64(y1-y2), 2))
}

func flush() {
	e := wtr.Flush()
	if e != nil {
		panic(e)
	}
	if rec := recover(); rec != nil {
		fmt.Printf("panic: %+v\n", rec)
		fmt.Printf("stackTrace: %+v\n", stackTrace())
	}
}

func stackTrace() string {
	stackTrace := ""
	for depth := 0; ; depth++ {
		_, file, line, ok := runtime.Caller(depth)
		if !ok {
			break
		}
		stackTrace += fmt.Sprintf("%02d: %v:%d\n", depth+1, file, line)
	}
	return stackTrace
}

func print(v ...interface{}) {
	_, e := fmt.Fprintln(wtr, v...)
	if e != nil {
		panic(e)
	}
}

func printInts(sl []int) {
	r := make([]string, len(sl))
	for i, v := range sl {
		r[i] = iToS(v)
	}
	print(strings.Join(r, " "))
}

func printInts64(sl []int64) {
	r := make([]string, len(sl))
	for i, v := range sl {
		r[i] = i64ToS(v)
	}
	print(strings.Join(r, " "))
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		new Main().main();
	}
	InputReader in;
	PrintWriter out;
	Random rand = new Random();
	
	void main()
	{
		in = new InputReader(System.in);
		out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		try
		{
			this.solve();
		}
		finally
		{
			out.close();
		}
	}
	int n,m;
	long[][] adj;
	boolean[] used;
	
	long walk(int from, int to, long len)
	{
		if(from == to)
			return len;
		if(used[from])
			return -1;
		used[from] = true;
	
		long res = -1;
		
		for(int nxt = 1;nxt <n; nxt++)
		{
			if(adj[from][nxt] != -1)
			{
				long best = walk(nxt, to, len^adj[from][nxt]);
				if( best != -1 && (res == -1 || res > best))
					res = best;
			}
		}
		
		
		used[from] = false;
		
		return res;
	}
	
	void solve()
	{
		n = in.nextInt();
		m = in.nextInt();
		adj = new long[n][n];
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				adj[i][j] = -1;
		used = new boolean[n];
	
		for(int i=0;i<m;i++)
		{
			int u = in.nextInt()-1;
			int w = in.nextInt()-1;
			long c = in.nextLong();
			adj[u][w] = adj[w][u] = c;
		}
		
		out.println(walk(0,n-1,0));
	}
	
	void safeSort(int[] arr)
	{
		shuffle(arr);
		Arrays.sort(arr);
	}
	
	void shuffle(int[] arr)
	{
		for(int i=arr.length;i>1;i--)
		{
			int pos = rand.nextInt(i);
			int tmp = arr[pos];
			arr[pos] = arr[i-1];
			arr[i-1] = tmp;
		}
	}

}

class InputReader
{
	private BufferedReader reader;
	private StringTokenizer token;
	
	public InputReader(InputStream in)
	{
		reader = new BufferedReader(new InputStreamReader(in));
		token = new StringTokenizer("");
	}
	
	public boolean hasNext() 
	{
		try
		{
			while(!token.hasMoreTokens())
			{
				String s = reader.readLine();
				if ( s != null )
					token = new StringTokenizer(s);
				else
					break;
			}
		}catch (IOException e) {
		}
		return token.hasMoreTokens();
	}
	
	String next()
	{
		hasNext();
		return token.nextToken();
	}
	
	int nextInt()
	{
		return Integer.parseInt(next());
	}
	
	int[] nextInts(int n)
	{
		int[] a = new int[n];
		for(int i=0;i<n;i++)
			a[i] = nextInt();
		return a;
	}
	
	long nextLong()
	{
		return Long.parseLong(next());
	}
}

JavaScript solution:
function Main(input) {
    input = input.split("\n").map(e => e.split(" "));
    const [N, M] = input.shift().map(Number);
    const edges = Array.from({ length: N + 1 }, () => new Map());
    for (let i = 0; i < M; i++) {
        const uvm = input[i];
        const u = Number(uvm[0]);
        const v = Number(uvm[1]);
        const m = BigInt(uvm[2]);
        edges[u].set(v, m);
        edges[v].set(u, m);
    }
    let ans = 1n << 60n;
    function dfs(now, visited, xor) {
        if (now === N) {
            if (xor < ans) ans = xor;
        } else {
            for (const [nex, add] of edges[now].entries()) {
                if (!(visited & 1 << nex)) dfs(nex, visited + (1 << nex), xor ^ add);
            }
        }
    }
    dfs(1, 2, 0n);
    console.log(ans + "");
}
Main(require("fs").readFileSync(0)+"")

Python solution:
import sys
sys.setrecursionlimit(10000)

# 入力
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]  # 1-indexed

for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))

# DFSで全単純パス探索
min_xor = float('inf')
visited = [False] * (N + 1)

def dfs(node, xor_sum):
    global min_xor
    if node == N:
        min_xor = min(min_xor, xor_sum)
        return
    visited[node] = True
    for neighbor, weight in graph[node]:
        if not visited[neighbor]:
            dfs(neighbor, xor_sum ^ weight)
    visited[node] = False  # backtrack

dfs(1, 0)

# 出力
print(min_xor)

Ruby solution:
# frozen_string_literal: true

n, m = gets.split.map(&:to_i)
uvw = Array.new(m) { gets.split.map(&:to_i) }

ww = Array.new(n) { Array.new(n, -1) }
g = Array.new(n) { [] }

uvw.each do |u, v, w|
  ww[u - 1][v - 1] = w
  ww[v - 1][u - 1] = w
  g[u - 1] << v - 1
  g[v - 1] << u - 1
end
INF = 2**62
@ans = INF

def dfs(v, g, done, xor, n, ww)
  #pp ['v, xor = ', v, xor]
  if v == n - 1
    @ans = xor if @ans > xor
    return
  end
  g[v].each do |nv|
    next if done[nv]

    done[nv] = true
    dfs(nv, g, done, xor == -1 ? ww[v][nv] : (xor ^ ww[v][nv]), n, ww)
    done[nv] = false
  end
end
done = Array.new(n, false)
done[0] = true
dfs(0, g, done, -1, n, ww)
puts @ans