vertex multiplexing을 이용한 가중치의 bitwise xor이 최소가 되는 경로

https://atcoder.jp/contests/abc410/tasks/abc410_d

D - XOR Shortest Walk

 

방향 그래프가 주어지는데, A에서 B로 가는 간선의 가중치가 W이다.

 

이때, 1번부터 N번 정점까지 경로의 가중치들의 bitwise xor이 최소가 되는 경로에 대해 그 최솟값을 구하면?

 

여기서 1번부터 N번 정점까지 경로는, 동일한 간선이나 동일한 정점을 여러번 방문하더라도, 처음 시작점이 1번이고 마지막 종점이 N번인 경로이다.

 

----------------------------------------------------------------------------------------------------------------------------------------------

 

vertex multiplexing이라고 불리는 기법으로 해결할 수 있다.

 

어떤 새로운 그래프 G는 정점을 (1,0),(1,1),....,(1,1023),(2,0),(2,1),...,(2,1023),....,(N,0),(N,1),...,(N,1023)으로 N*1024개의 정점을 가진다고 하자.

 

주어진 그래프가 A에서 B로 가는 간선이 존재하고, 이때 가중치가 W라고 한다면....

 

새로운 그래프 G는 (A,S)에서 (B,S XOR W)로 가는 간선이 존재한다.

 

그러면 새로운 그래프 G에서 (1,0)에서 (N,0),(N,1),...,(N,1023)으로 도달할 수 있는지 체크하면 된다.

 

이때, (N,?)에 도달할 수 있다면, 그 경로의 모든 가중치간 XOR값은 ?가 된다.

 

따라서 도달한 정점 중 최소 XOR값을 찾을 수 있다.

 

총 (N*1024)개의 정점이 있고 원래 그래프의 간선 1개당, 1024개가 생기므로, (M*1024)개의 간선을 가지는 그래프 G에서 BFS를 수행하여 찾을 수 있다.

 

 

 

 

 

from collections import deque

n,m = map(int,input().split())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    
    a,b,w = list(map(int,input().split()))
    graph[a].append((b,w))

graph2 = [[[] for _ in range(1024)] for _ in range(n+1)]

for i in range(1,n+1):
    
    for j in range(1024):
        
        for y,w in graph[i]:
            
            graph2[i][j].append((y,j^w))

queue = deque([(1,0)])
visited = [[0]*1024 for _ in range(n+1)]
visited[1][0] = 1

INF = 10**12
min_v = INF

while queue:
    
    x,y = queue.popleft()

    for v,s in graph2[x][y]:

        if visited[v][s] == 0:
            
            visited[v][s] = 1
            queue.append((v,s))

            if v == n:
                
                if min_v > s:
                    
                    min_v = s

if min_v == INF:
    
    print(-1)

else:
    
    print(min_v)

 

 

여기서 중요한건 중간에 N번에 도달하더라도, 나중에 N번에 도달할 수 있다는 점임

 

그래서, 이렇게 구현하면 WA를 받는다

 

while queue:
    
    x,y = queue.popleft()

    for v,s in graph2[x][y]:

        if visited[v][s] == 0:

            if v == n:
                
                if min_v > s:
                    
                    min_v = s
            
            else:
                
                visited[v][s] = 1
                queue.append((v,s))