Submission #66768895

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 線形基底ライブラリ
def insert_basis(basis, x):
    """10bit 線形基底へ x を挿入する（破壊的）。
       basis[i] は bit i が立つ代表ベクトル（0=空）。"""
    for bit in range(9, -1, -1):
        if not (x >> bit) & 1:
            continue
        if basis[bit]:
            x ^= basis[bit]
        else:
            basis[bit] = x
            break
def minimize_with_basis(basis, val):
    """basis で val を最小化した値を返す"""
    for bit in range(9, -1, -1):
        if basis[bit] and val > (val ^ basis[bit]):
            val ^= basis[bit]
    return val
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

# 線形基底ライブラリ
def insert_basis(basis, x):
    """10bit 線形基底へ x を挿入する（破壊的）。
       basis[i] は bit i が立つ代表ベクトル（0=空）。"""
    for bit in range(9, -1, -1):
        if not (x >> bit) & 1:
            continue
        if basis[bit]:
            x ^= basis[bit]
        else:
            basis[bit] = x
            break


def minimize_with_basis(basis, val):
    """basis で val を最小化した値を返す"""
    for bit in range(9, -1, -1):
        if basis[bit] and val > (val ^ basis[bit]):
            val ^= basis[bit]
    return val


N, M = map(int, input().split())

G = [[] for _ in range(N)]
for _ in range(M):
    A, B, W = map(int, input().split())
    A -= 1
    B -= 1
    G[A].append((B, W))

INF = float('inf')

dist = [INF] * N
dist[0] = 0

basis = [0] * 10
stack = [0]

while stack:
    u = stack.pop()
    for v, w in G[u]:
        if dist[v] == INF:
            dist[v] = dist[u] ^ w
            stack.append(v)
        else:
            cycle = dist[u] ^ w ^ dist[v]
            if cycle:
                insert_basis(basis, cycle)

if dist[N - 1] == INF:
    print(-1)
else:
    ans = minimize_with_basis(basis, dist[N - 1])
    print(ans)

Submission Info

Judge Result