Submission #66751926

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque
n, m = map(int, input().split())
p = [[*map(int, input().split())] for _ in range(m)]
g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for i in range(m):
    a, b, w = p[i]
    a -= 1
    b -= 1
    g[a].append([b, w])
    rg[b].append(a)
visited = [False] * n
dq = deque([0])
visited[0] = True
while dq:
    u = dq.popleft()
    for v, _ in g[u]:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque

n, m = map(int, input().split())
p = [[*map(int, input().split())] for _ in range(m)]


g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for i in range(m):
    a, b, w = p[i]
    a -= 1
    b -= 1
    g[a].append([b, w])
    rg[b].append(a)

visited = [False] * n
dq = deque([0])
visited[0] = True
while dq:
    u = dq.popleft()
    for v, _ in g[u]:
        if not visited[v]:
            visited[v] = True
            dq.append(v)

if not visited[n - 1]:
    print(-1)
    exit()

# 逆向きを考えて1->Nへのパスを保証する
reverse_visited = [False] * n
dq = deque([n - 1])
reverse_visited[n - 1] = True
while dq:
    u = dq.popleft()
    for v in rg[u]:
        if not reverse_visited[v]:
            reverse_visited[v] = True
            dq.append(v)


seen = [False] * n
d = [0] * n
dq = deque([0])
seen[0] = True
while dq:
    u = dq.popleft()
    for v, w in g[u]:
        if not (visited[v] and reverse_visited[v]):
            continue
        if not seen[v]:
            seen[v] = True
            d[v] = d[u] ^ w
            dq.append(v)

max_xor = max((w for _, _, w in p))
max_length = max(max_xor.bit_length(), d[n - 1].bit_length())
basis = [0] * (max_length + 1)

for u, v, w in p:
    u -= 1
    v -= 1
    if visited[u] and visited[v] and reverse_visited[u] and reverse_visited[v]:
        c = d[u] ^ w ^ d[v]
        if c:
            for b in range(max_length, -1, -1):
                if not (c >> b) & 1:
                    continue
                if basis[b] == 0:
                    basis[b] = c
                    break
                c ^= basis[b]

ans = d[-1]
for b in range(max_length, -1, -1):
    if basis[b] and (ans ^ basis[b]) < ans:
        ans ^= basis[b]

print(ans)

Submission Info

Judge Result