Submission #66759619

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, math, bisect, itertools, pprint, collections
from collections import deque, defaultdict
from heapq import heappush, heappop, heapify
from sortedcontainers import SortedSet, SortedList, SortedDict
###おまじない
input = sys.stdin.readline
INF = 10 ** 20
sys.setrecursionlimit(10 ** 8)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
N, M = map(int, input().split())
tmp = [list(map(int, input().split())) for _ in range(M)]
A = [t[0] for t in tmp]
B = [t[1] for t in tmp]
W = [t[2] for t in tmp]
graph = [[] for _ in range(N)]
for i in range(M):
    graph[A[i] - 1].append((B[i] - 1, W[i]))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys, math, bisect, itertools, pprint, collections
from collections import deque, defaultdict
from heapq import heappush, heappop, heapify
from sortedcontainers import SortedSet, SortedList, SortedDict

###おまじない
input = sys.stdin.readline
INF = 10 ** 20
sys.setrecursionlimit(10 ** 8)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')

N, M = map(int, input().split())
tmp = [list(map(int, input().split())) for _ in range(M)]
A = [t[0] for t in tmp]
B = [t[1] for t in tmp]
W = [t[2] for t in tmp]

graph = [[] for _ in range(N)]
for i in range(M):
    graph[A[i] - 1].append((B[i] - 1, W[i]))

dist = [-1] * N
basis = []

def dfs(u):
    for v, w in graph[u]:
        path_xor_to_v = dist[u] ^ w
        if dist[v] == -1:
            dist[v] = path_xor_to_v
            dfs(v)
        else:
            cycle_xor = path_xor_to_v ^ dist[v]
            if cycle_xor > 0:
                for i in basis:
                    cycle_xor = min(cycle_xor, cycle_xor ^ i)
                if cycle_xor > 0:
                    basis.append(cycle_xor)

dist[0] = 0
dfs(0)

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

Submission Info

Judge Result