Submission #66772861

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
input = sys.stdin.readline
def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v, w = map(int, input().split())
        g[u-1].append((v-1, w))
    dist = [None]*n
    dist[0] = 0
    basis = []
    stack = [0]
    while stack:
        u = stack.pop()
        for v, w in g[u]:
            x = dist[u] ^ w
            if dist[v] is None:
                dist[v] = x
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v, w = map(int, input().split())
        g[u-1].append((v-1, w))

    dist = [None]*n
    dist[0] = 0
    basis = []
    stack = [0]

    while stack:
        u = stack.pop()
        for v, w in g[u]:
            x = dist[u] ^ w
            if dist[v] is None:
                dist[v] = x
                stack.append(v)
            else:
                y = x ^ dist[v]
                for b in sorted(basis, reverse=True):
                    y = min(y, y ^ b)
                if y:
                    basis.append(y)

    if dist[-1] is None:
        print(-1)
        return

    res = dist[-1]
    for b in sorted(basis, reverse=True):
        res = min(res, res ^ b)
    print(res)

if __name__ == "__main__":
    main()

Submission Info

Judge Result