Submission #66770437

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N,M=map(int,input().split())
G=[[] for _ in range(N)]
for i in range(M):
    a,b,w=map(int, input().split())
    a-=1
    b-=1
    G[a].append((b,w))
seen=[False]*N
dist=[0]*N
bas=[]
st=[(0,0)]
seen[0]=True
while st:
    u,idx=st.pop()
    if idx<len(G[u]):
        st.append((u,idx+1))
        v,w=G[u][idx]
        if not seen[v]:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N,M=map(int,input().split())
G=[[] for _ in range(N)]
for i in range(M):
    a,b,w=map(int, input().split())
    a-=1
    b-=1
    G[a].append((b,w))

seen=[False]*N
dist=[0]*N
bas=[]

st=[(0,0)]
seen[0]=True
while st:
    u,idx=st.pop()
    if idx<len(G[u]):
        st.append((u,idx+1))
        v,w=G[u][idx]
        if not seen[v]:
            seen[v]=True
            dist[v]=dist[u]^w
            st.append((v,0))
        else:
            c=dist[u]^w^dist[v]
            for b in bas:
                c=min(c,c^b)
                
            if c:
                bas.append(c)
                bas.sort(reverse=True)
                
                for i in range(len(bas)):
                    for j in range(i+1,len(bas)):
                        bas[j]=min(bas[j],bas[j]^bas[i])


if not seen[-1]:
    print(-1)
    exit()

    
ans=dist[-1]
for b in bas:
    ans=min(ans,ans^b)
print(ans)

Submission Info

Judge Result