Submission #66779542

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
  a, b, w = map(int, input().split())
  g[a-1].append([b-1, w])
xor_to = [-1 for _ in range(n)]
ba = []
def add_to_ba(x):
  for b in ba:
    x = min(x, x ^ b)
  if x:
    ba.append(x)
def dfs(p, xor):
  xor_to[p] = xor
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys

sys.setrecursionlimit(10**9)

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

xor_to = [-1 for _ in range(n)]
ba = []

def add_to_ba(x):
  for b in ba:
    x = min(x, x ^ b)
  if x:
    ba.append(x)

def dfs(p, xor):
  xor_to[p] = xor
  for gp in g[p]:
    if xor_to[gp[0]] == -1:
      dfs(gp[0], xor ^ gp[1])
    else:
      xor_c = xor ^ xor_to[gp[0]] ^ gp[1]
      add_to_ba(xor_c)
dfs(0, 0)  
ans = xor_to[n-1]
bsl = sorted(ba, reverse=True)
for bs in bsl:
  ans = min(ans, ans ^ bs)
  
print(ans if ans >= 0 else -1)

Submission Info

Judge Result