Submission #66765129

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
sys.setrecursionlimit(2000)
input = sys.stdin.readline
class XORBasis:
    def __init__(self):
        self.basis = []
        self.size = 0
    def add(self,val):
        for b in self.basis:
            val = min(val,val^b)
        if val>0:
            self.basis.append(val)
            self.basis.sort(reverse= True)
            self.size += 1
    def minimize(self,val):
        for b in self.basis:
            val = min(val,val^b)
        return val
    
def main():
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys
sys.setrecursionlimit(2000)
input = sys.stdin.readline

class XORBasis:
    def __init__(self):
        self.basis = []
        self.size = 0
    def add(self,val):
        for b in self.basis:
            val = min(val,val^b)
        if val>0:
            self.basis.append(val)
            self.basis.sort(reverse= True)
            self.size += 1
    def minimize(self,val):
        for b in self.basis:
            val = min(val,val^b)
        return val
    
def main():
    n,m = map(int,input().split())
    graph = [[] for _ in range(n+1)]

    for _ in range(m):
        a,b,w = map(int,input().split())
        graph[a].append((b,w))
        graph[b].append((a,w))
    
    dist = [-1]*(n+1)
    basis = XORBasis()
    def dfs(u,current_xor):
        dist[u] = current_xor
        for v,w in graph[u]:
            if dist[v] != -1:
                cycle = current_xor ^ w ^ dist[v]
                if cycle > 0:
                    basis.add(cycle)
            
            else:
                dfs(v,current_xor ^ w)  
    dfs(1,0)

    if dist[n] == -1:
        print(-1)
    
    else:
        path = dist[n]
        min_sum = basis.minimize(path)
        print(min_sum)

if __name__ == "__main__":
    main()

Submission Info

Judge Result