Submission #66745186

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 ** 8)
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
dist = [-1] * (N + 1)
basis = []
def insert_basis(x):
    for b in basis:
        x = min(x, x ^ b)
    if x != 0:
        basis.append(x)
        basis.sort(reverse=True)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys

sys.setrecursionlimit(10 ** 8)

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

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

dist = [-1] * (N + 1)
basis = []


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


def dfs(v, xor_val):
    dist[v] = xor_val
    for to, w in graph[v]:
        next_xor = xor_val ^ w
        if dist[to] == -1:
            dfs(to, next_xor)
        else:
            insert_basis(dist[to] ^ next_xor)


dfs(1, 0)

if dist[N] == -1:
    print(-1)
else:
    ans = dist[N]
    for b in basis:
        ans = min(ans, ans ^ b)
    print(ans)

Submission Info

Judge Result