Submission #66765339

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#合わないなと思ったらケース違った
#Why?
#有向グラフですかそうですか……
#まだあるんですか……
#サイクルを成すかの条件がビミョいので逆向きグラフを作る
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
rgraph = [[] for _ in range(N)]
for i in range(M):
    a,b,w = map(int,input().split())
    a -= 1; b -= 1
    graph[a].append((b,w))
    rgraph[b].append(a)
dist = [None]*N
dist[0] = 0
can_go_N = [False]*N
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#合わないなと思ったらケース違った
#Why?

#有向グラフですかそうですか……
#まだあるんですか……
#サイクルを成すかの条件がビミョいので逆向きグラフを作る

N,M = map(int,input().split())
graph = [[] for _ in range(N)]
rgraph = [[] for _ in range(N)]

for i in range(M):
    a,b,w = map(int,input().split())
    a -= 1; b -= 1
    graph[a].append((b,w))
    rgraph[b].append(a)

dist = [None]*N
dist[0] = 0

can_go_N = [False]*N



from collections import deque
queue = deque()
can_go_N[-1] = True
queue.append(N-1)
while queue:
    u = queue.popleft()
    for v in rgraph[u]:
        if not can_go_N[v]:
            can_go_N[v] = True
            queue.append(v)


values = []
def dfs(u):
    stack = [u]
    while stack:
        u = stack.pop()
        for v,w in graph[u]:
            if not can_go_N[v]:
                continue
            if dist[v] == None:
                dist[v] = dist[u]^w
                stack.append(v)
            else:
                x = dist[u]^dist[v]^w
                if x:
                    values.append(x)




if can_go_N[0] == False:
    exit(print(-1))
else:
    dfs(0)
if dist[N-1] == None:
    exit(print(-1))

bit = [0]*60

for x in values:
    v = x
    for b in range(60-1,-1,-1):
        if not (v>>b)&1:
            continue
        if bit[b] == 0:
            bit[b] = v
            break
        v ^= bit[b]

ans = dist[N-1]
for b in range(60-1,-1,-1):
    if bit[b] and (ans^bit[b]) < ans:
        ans ^=bit[b]
print(ans)

Submission Info

Judge Result