Submission #66739568

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())
    a-=1
    b-=1
    G[a].append((b,w))
    G[b].append((a,w))
dist=[-1]*N
dist[0]=0
q=deque()
q.append(0)
while q:
    v=q.popleft()
    for nv,w in G[v]:
        if dist[nv]==-1:
            dist[nv]=dist[v]^w
            q.append(nv)
basis=[]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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())
    a-=1
    b-=1
    G[a].append((b,w))
    G[b].append((a,w))
dist=[-1]*N
dist[0]=0
q=deque()
q.append(0)
while q:
    v=q.popleft()
    for nv,w in G[v]:
        if dist[nv]==-1:
            dist[nv]=dist[v]^w
            q.append(nv)
basis=[]
visited=[False]*N
def dfs(v):
    visited[v]=True
    for nv,w in G[v]:
        if dist[nv] != -1:
            cycle=dist[v]^w^dist[nv]
            if cycle != 0:
                for b in basis:
                    cycle=min(cycle,cycle^b)
                if cycle != 0:
                    basis.append(cycle)
        else:
            dist[nv]=dist[v]^w
            dfs(nv)
dist=[-1]*N
dist[0]=0
dfs(0)
ans=dist[N - 1]
if ans==-1:
    print(-1)
else:
    for b in basis:
        ans=min(ans,ans^b)
    print(ans)

Submission Info

Judge Result