Submission #66774382

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
from collections import deque
def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        a = int(input[ptr])
        ptr += 1
        b = int(input[ptr])
        ptr += 1
        w = int(input[ptr])
        ptr += 1
        adj[a].append((b, w))
    
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        a = int(input[ptr])
        ptr += 1
        b = int(input[ptr])
        ptr += 1
        w = int(input[ptr])
        ptr += 1
        adj[a].append((b, w))
    
    INF = 1 << 60
    dist = [INF] * (N + 1)
    dist[1] = 0
    q = deque([1])
    
    while q:
        u = q.popleft()
        for (v, w) in adj[u]:
            if dist[v] == INF:
                dist[v] = dist[u] ^ w
                q.append(v)
    
    if dist[N] == INF:
        print(-1)
        return
    basis = []
    
    def add_to_basis(x):
        for b in basis:
            x = min(x, x ^ b)
        if x != 0:
            basis.append(x)
            basis.sort(reverse=True)
    for u in range(1, N+1):
        if dist[u] == INF:
            continue
        for (v, w) in adj[u]:
            if dist[v] != INF:
                cycle_xor = dist[u] ^ w ^ dist[v]
                add_to_basis(cycle_xor)
    
    res = dist[N]
    for b in basis:
        res = min(res, res ^ b)
    print(res)

if __name__ == '__main__':
    main()

Submission Info

Judge Result