Submission #66738862

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
N,M=map(int, input().split())
G=[[] for _ in range(N)]
for _ in range(M):
    a,b,w=map(int, input().split())
    G[a-1].append((b-1,w))
dist=[-1]*N
dist[0]=0
que=deque()
que.append(0)
base=[]
while que:
    u=que.popleft()
    for v,c in G[u]:
        x=dist[u]^c
        if dist[v]==-1:
            dist[v]=x
            que.append(v)
        else:
            cycle=dist[v]^x
            if cycle!=0:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque
N,M=map(int, input().split())
G=[[] for _ in range(N)]
for _ in range(M):
    a,b,w=map(int, input().split())
    G[a-1].append((b-1,w))
dist=[-1]*N
dist[0]=0
que=deque()
que.append(0)
base=[]
while que:
    u=que.popleft()
    for v,c in G[u]:
        x=dist[u]^c
        if dist[v]==-1:
            dist[v]=x
            que.append(v)
        else:
            cycle=dist[v]^x
            if cycle!=0:
                for b in base:
                    cycle=min(cycle,cycle^b)
                if cycle!=0:
                    base.append(cycle)
if dist[N-1]==-1:
    print(-1)
else:
    ans=dist[N-1]
    for b in base:
        ans=min(ans,ans^b)
    print(ans)

Submission Info

Judge Result