Submission #66779903

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
def main():
    N, M = map(int, input().split())
    
    C = [[] for _ in range(N)]
    for _ in range(M):
        a, b, w = map(int, input().split())
        a, b = a - 1, b - 1
        C[a].append((b, w))
    seen = [False] * N
    dfs = deque()
    # (node, xor)
    dfs.append((0, 0))
    seen[0] = True
    
    cycle1 = [0]
    path = []
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque

def main():
    N, M = map(int, input().split())
    
    C = [[] for _ in range(N)]

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

    seen = [False] * N

    dfs = deque()
    # (node, xor)
    dfs.append((0, 0))
    seen[0] = True
    
    cycle1 = [0]
    path = []
    
    while dfs:
        node, xor = dfs.pop()
        for to, cost in C[node]:
            if to == 0:
                cycle1.append((xor ^ cost))
            
            elif to == N - 1:
                path.append((xor ^ cost))

            else:
                if not seen[to]:
                    seen[to] = True
                    dfs.append((to, xor ^ cost))

    dfs = deque()
    dfs.append((N-1, 0))
    seen = [False] * N
    seen[N-1] = True
    cycleN = [0]
    while dfs:
        node, xor = dfs.pop()
        for to, cost in C[node]:
            if to == N - 1:
                cycleN.append((xor ^ cost))
            else:
                if not seen[to]:
                    seen[to] = True
                    dfs.append((to, xor ^ cost))

    # print(cycle1)
    # print(path)
    # print(cycleN)

    if len(path) == 0:
        print(-1)
    else:
        ans = 10 ** 18
        for c1 in cycle1:
            for p in path:
                for cN in cycleN:
                    ans = min(ans, c1 ^ p ^ cN)
        print(ans)

    return

main()

Submission Info

Judge Result