Submission #66774120

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N, M = map(int, input().split())
G, W = [[] for _ in range(N)], [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, w = map(int, input().split())
    G[a - 1].append(b - 1)
    W[a - 1][b - 1] = w
import sys
sys.setrecursionlimit(10**7)
def min_xor_walk(adj, W):
    N = len(adj)
    dist = [None] * N
    dist[0] = 0
    basis = []
    def insert_basis(x):
        for b in basis:
            x = min(x, x ^ b)
        if x:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N, M = map(int, input().split())
G, W = [[] for _ in range(N)], [[0] * N for _ in range(N)]
for _ in range(M):
    a, b, w = map(int, input().split())
    G[a - 1].append(b - 1)
    W[a - 1][b - 1] = w

import sys
sys.setrecursionlimit(10**7)

def min_xor_walk(adj, W):
    N = len(adj)
    dist = [None] * N
    dist[0] = 0

    basis = []

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

    def dfs(u):
        for v in adj[u]:
            x = dist[u] ^ W[u][v]
            if dist[v] is None:
                dist[v] = x
                dfs(v)
            else:
                insert_basis(x ^ dist[v])

    dfs(0)

    if dist[N-1] is None:
        return None

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

ans = min_xor_walk(G, W)
if ans is None:
    print(-1)
else:
    print(ans)

Submission Info

Judge Result