Submission #66752638

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 
def input():return sys.stdin.readline().rstrip()
def main():
    import networkx as nx
    
    n, m = map(int, input().split())
    g = nx.DiGraph()
    g.add_nodes_from(range(1, n+1))
    for _ in range(m):
        a, b, w = map(int, input().split())
        g.add_edge(a, b, weight=w)
    
    dist = {i: None for i in range(1, n+1)}
    dist[1] = 0
    stack = [1]
    cycle = []
    while stack:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys 


def input():return sys.stdin.readline().rstrip()


def main():
    import networkx as nx
    
    n, m = map(int, input().split())
    g = nx.DiGraph()
    g.add_nodes_from(range(1, n+1))
    for _ in range(m):
        a, b, w = map(int, input().split())
        g.add_edge(a, b, weight=w)
    
    dist = {i: None for i in range(1, n+1)}
    dist[1] = 0
    stack = [1]
    cycle = []
    while stack:
        u = stack.pop()
        for v in g[u]:
            w = g[u][v]['weight']
            x = dist[u] ^ w
            
            if dist[v] is None:
                dist[v] = x
                stack.append(v)
            else:
                cycle.append(x^dist[v])
    
    if dist[n] is None:
        print(-1); return
    bit = []
    for x in cycle:
        for b in bit: 
            x = min(x, x^b)
        if x: 
            bit.append(x)

    ans = dist[n]
    for b in bit: 
        ans = min(ans, ans^b)
    print(ans)

    

if __name__ == '__main__':
    sys.exit(main())

Submission Info

Judge Result