Submission #66772624

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))
flag=[0]*N
dist=[0]*N
bas=[]
st=[(0,0)]
flag[0]=1
dist[0]=0
while st:
    u,idx=st[-1]
    if idx<len(G[u]):
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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))

flag=[0]*N
dist=[0]*N
bas=[]


st=[(0,0)]
flag[0]=1
dist[0]=0

while st:
    u,idx=st[-1]
    if idx<len(G[u]):
        v,w=G[u][idx]
        st[-1]=(u,idx+1)

        if flag[v]==0:
            flag[v]=1
            dist[v]=dist[u]^w
            st.append((v,0))
        elif flag[v]==1:
            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])
    else:
        flag[u]=2
        st.pop()


if flag[-1]==0:
    print(-1)
    exit()


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

Submission Info

Judge Result