Submission #66787076

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import defaultdict, deque
def insert_basis(basis, x):
    for b in basis:
        x = min(x, x ^ b)
    if x:
        basis.append(x)
        basis.sort(reverse=True)  # optional
    return basis
n, m = map(int, input().split())
d = defaultdict(list)
for _ in range(m):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append((b, w))
    d[b].append((a, w))
visited = [None] * n
basis = []
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import defaultdict, deque

def insert_basis(basis, x):
    for b in basis:
        x = min(x, x ^ b)
    if x:
        basis.append(x)
        basis.sort(reverse=True)  # optional
    return basis

n, m = map(int, input().split())
d = defaultdict(list)
for _ in range(m):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append((b, w))
    d[b].append((a, w))

visited = [None] * n
basis = []

que = deque([(0, 0)])
visited[0] = 0

while que:
    v, xor_val = que.popleft()
    for u, w in d[v]:
        new_xor = xor_val ^ w
        if visited[u] is None:
            visited[u] = new_xor
            que.append((u, new_xor))
        else:
            cycle_xor = new_xor ^ visited[u]
            basis = insert_basis(basis, cycle_xor)

# 到達不可
if visited[n - 1] is None:
    print(-1)
else:
    res = visited[n - 1]
    for b in basis:
        res = min(res, res ^ b)
    print(res)

Submission Info

Judge Result