Submission #66746991

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

from collections import deque, defaultdict

N, M = map(int, input().split())
graph = defaultdict(list)

for _ in range(M):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
    
dist = [-1] * (N + 1)
dist[1] = 0

MIN = []

def XOR(x):
    for i in MIN:
        x = min(x, x ^ i)
    if x:
        MIN.append(x)
        MIN.sort(reverse=True)

q = deque()
q.append(1)

visited = defaultdict(bool)

while q:
    u = q.popleft()
    for v, w in graph[u]:
        if dist[v] == -1:
            dist[v] = dist[u] ^ w
            q.append(v)
        else:
            k = dist[u] ^ w ^ dist[v]
            XOR(k)

if dist[N] == -1:
    print(-1)
else:
    a = dist[N]
    for i in MIN:
        a = min(a, a ^ i)
    print(a)

Submission Info

Judge Result