Submission #66766258

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(10**6)
def main():
    input = sys.stdin.readline
    try:
        N, M = map(int, input().split())
    except ValueError:
        return
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b, w = map(int, input().split())
        graph[a].append((b, w))
    dist = [-1] * (N + 1)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys

sys.setrecursionlimit(10**6)


def main():
    input = sys.stdin.readline

    try:
        N, M = map(int, input().split())
    except ValueError:
        return

    graph = [[] for _ in range(N + 1)]

    for _ in range(M):
        a, b, w = map(int, input().split())
        graph[a].append((b, w))

    dist = [-1] * (N + 1)

    cycle_values = []

    def dfs(u):
        for v, w in graph[u]:
            if dist[v] != -1:  
                cycle_xor = dist[u] ^ w ^ dist[v]
                cycle_values.append(cycle_xor)
            else:
                dist[v] = dist[u] ^ w
                dfs(v)

    dist[1] = 0
    dfs(1)

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

    basis = []
    for val in cycle_values:
        for b in basis:
            val = min(val, val ^ b)
        if val > 0:
            basis.append(val)

    min_xor_path = dist[N]

    for b in basis:
        min_xor_path = min(min_xor_path, min_xor_path ^ b)

    print(min_xor_path)


if __name__ == "__main__":
    main()

Submission Info

Judge Result