Submission #66767401

Source Code Expand

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

n, m = map(int, input().split())
g = [[] for _ in range(n)]

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

sys.setrecursionlimit(10**6)
dist = [-1] * n
cyc = []


def dfs(u):
    for v, w in g[u]:
        if dist[v] == -1:
            dist[v] = dist[u] ^ w
            dfs(v)
        else:
            cyc.append(dist[u] ^ w ^ dist[v])


dist[0] = 0
dfs(0)
if dist[-1]<0:exit(print(-1))
base = []
for x in cyc:
    for b in base:
        x = min(x ^ b, x)
    if x:
        base.append(x)
        base.sort(reverse=True)
ans = dist[-1]
for b in base:
    ans = min(ans, ans ^ b)
print(ans)

Submission Info

Judge Result