Submission #66780262

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
n, m = map(int, input().split())
a = [0] * m
b = [0] * m
w = [0] * m
for i in range(m):
    a[i], b[i], w[i] = map(int, input().split())
g = defaultdict(list)
for i in range(m):
    g[a[i]].append((b[i], w[i]))
    g[b[i]].append((a[i], w[i]))
d = [-1] * (n + 1)
d[1] = 0
s = [1]
c = []
while s:
    u = s.pop()
    for v, x in g[u]:
        if d[v] == -1:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import defaultdict

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
w = [0] * m
for i in range(m):
    a[i], b[i], w[i] = map(int, input().split())
g = defaultdict(list)
for i in range(m):
    g[a[i]].append((b[i], w[i]))
    g[b[i]].append((a[i], w[i]))
d = [-1] * (n + 1)
d[1] = 0
s = [1]
c = []

while s:
    u = s.pop()
    for v, x in g[u]:
        if d[v] == -1:
            d[v] = d[u] ^ x
            s.append(v)
        else:
            y = d[u] ^ x ^ d[v]
            z = y
            for b in c:
                z = min(z, z ^ b)
            if z != 0:
                c.append(z)
                c.sort(reverse=True)
r = d[n]
for b in c:
    r = min(r, r ^ b)
print(r)

Submission Info

Judge Result