Submission #66757494

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/env python3
from collections import deque
# Generated by 2.14.0 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        A, B, W = map(int, input().split())
        G[A-1].append((B-1, W))
    dist = [-1] * N
    dist[0] = 0
    xor_basis = []
    que = deque([0])
    while que:
        v = que.popleft()
        for u, w in G[v]:
            if dist[u] == -1:
                dist[u] = dist[v] ^ w
                que.append(u)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#!/usr/bin/env python3
from collections import deque

# Generated by 2.14.0 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        A, B, W = map(int, input().split())
        G[A-1].append((B-1, W))
    dist = [-1] * N
    dist[0] = 0
    xor_basis = []

    que = deque([0])
    while que:
        v = que.popleft()
        for u, w in G[v]:
            if dist[u] == -1:
                dist[u] = dist[v] ^ w
                que.append(u)
            else:
                cycle_xor = dist[u] ^ dist[v] ^ w
                xor_basis.append(cycle_xor)

    if dist[N - 1] == -1:
        print(-1)
        return

    xor_basis_sorted = []

    def insert_basis(x):
        for b in xor_basis_sorted:
            x = min(x, x ^ b)
        if x:
            xor_basis_sorted.append(x)
            xor_basis_sorted.sort(reverse=True)

    for x in xor_basis:
        insert_basis(x)


    res = dist[N - 1]
    for b in xor_basis_sorted:
        res = min(res, res ^ b)

    print(res)

if __name__ == '__main__':
    main()

Submission Info

Judge Result