최단거리가 k의 배수가 되는 경로를 찾는 다익스트라 알고리즘

1. 문제

 

28131번: K-지폐 (acmicpc.net)

28131번: K-지폐

 

2. 풀이

 

문제 자체는 간단하다

 

s에서 t로 이동하는데 가중치의 합이 k의 배수가 되는 최단 경로를 찾는 문제

 

어떤 수가 k의 배수라는 것은, k로 나눈 나머지가 0이라는 사실을 이용해서 찾는다.

 

D[i][j]를 s에서 출발해서 i 정점으로 가는 경로의 가중치 합을 k로 나눈 나머지가 j가 되는 최소 가중치 합으로 정의하자

 

i에 연결된 정점 u에 대하여... u로 이동하는데 드는 간선의 비용이 w라고 한다면..

 

현재 i에서 가중치 합을 k로 나눈 나머지가 j일때, u로 가는데 드는 가중치 합을 k로 나눈 나머지는... y = (D[i][j] + w) %k으로 구한다.

 

그러므로, u로 가는데 드는 모든 비용의 합을 k로 나눈 나머지에 따라 최단 비용 테이블을

 

D[u][y] = min(D[i][j]+w)으로 구할 수 있다.

 

우선순위 큐가 빌때까지 다익스트라 알고리즘을 반복하면, k의 배수가 되는 최단경로는 D[t][0]에 들어가 있을것

 

왜냐하면 k의 배수라는 것은 k로 나눈 나머지가 0이니까

 

#비용이 k의 배수가 되는 최단 경로를 찾는 문제
import heapq
from sys import stdin

n,m,k = map(int,stdin.readline().split())

s,t = map(int,stdin.readline().split())

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

for _ in range(m):
    
    u,v,w = map(int,stdin.readline().split())

    graph[u].append((v,w))

queue = []

INF = 10000000000000000000000000000000

#distance[i][j] = s에서 i로 가는데 드는 비용 합을 k로 나눈 나머지가 j가 되는 비용의 합의 최솟값
distance = [[INF for _ in range(k)] for _ in range(n+1)]

distance[s][0] = 0

heapq.heappush(queue,(0,s))

while queue:
    
    dist,v = heapq.heappop(queue)

    if distance[v][dist % k] < dist:

        continue

    for u,w in graph[v]:
        
        cost = dist + w
        
        #s에서 u로 가는데 드는 비용의 합 cost를 k로 나눈 나머지에 따라, 최단 비용을 갱신 
        if distance[u][cost % k] > cost:
            
            distance[u][cost % k] = cost
            heapq.heappush(queue,(cost,u))

if distance[t][0] == INF:
    
    print('IMPOSSIBLE')

else:
    
    print(distance[t][0])

 

 

3. 문제2

 

20128번: Parity Constraint Shortest Path (acmicpc.net)

20128번: Parity Constraint Shortest Path

 

4. 풀이

 

위 문제에서 k=2인 특수한 경우이다..

 

위 문제를 안풀고 이 문제부터 풀었었는데 distance 배열을 u로 가는데 드는 비용의 합이 홀수, 짝수인 경우로 나눠 저장한다.

 

그리고 다익스트라 알고리즘을 수행할때 비용의 합 cost가 짝수이냐, 홀수이냐에 따라 distance[u][1]이냐, distance[u][0]냐에 따라 따로 최소 비용을 갱신했다

 

import heapq
from sys import stdin

n,m = map(int,stdin.readline().split())

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

for _ in range(m):
    
    u,v,w = map(int,stdin.readline().split())

    graph[u].append((v,w))
    graph[v].append((u,w))

queue = []

INF = 100000000000000000000000000000000000000

distance = [[INF,INF] for _ in range(n+1)]

distance[1] = [INF,0]

heapq.heappush(queue,(0,1))

while queue:
    
    dist,v = heapq.heappop(queue)

    if distance[v][0] < dist and distance[v][1] < dist:
        
        continue
    
    for u,w in graph[v]:
        
        cost = dist + w

        if cost % 2 == 0:
            
            if distance[u][1] > cost:
                
                distance[u][1] = cost
                heapq.heappush(queue,(cost,u))
        
        else:
            
            if distance[u][0] > cost:
                
                distance[u][0] = cost
                heapq.heappush(queue,(cost,u))


for i in range(1,n+1):
    
    if distance[i][0] == INF and distance[i][1] == INF:
        
        print(-1,-1)
    
    elif distance[i][0] == INF and distance[i][1] != INF:
        
        print(-1,distance[i][1])
    
    elif distance[i][0] != INF and distance[i][1] == INF:
        
        print(distance[i][0],-1)
    
    else:
        
        print(distance[i][0],distance[i][1])

 

 

근데 결국 k-지폐 문제처럼 k=2로 환원해서 다음과 같이 깔끔하게 풀린다..

 

#짝수 비용 최단 경로, 홀수 비용 최단 경로 찾기
#2의 배수가 되는 최단 경로를 찾는 문제
#k의 배수가 되는 최단 경로를 찾는 알고리즘에서 k = 2
import heapq
from sys import stdin

n,m = map(int,stdin.readline().split())

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

for _ in range(m):
    
    u,v,w = map(int,stdin.readline().split())

    graph[u].append((v,w))
    graph[v].append((u,w))

queue = []

INF = 100000000000000000000000000000000000000

distance = [[INF,INF] for _ in range(n+1)]

distance[1][0] = 0

heapq.heappush(queue,(0,1))

while queue:
    
    dist,v = heapq.heappop(queue)

    if distance[v][dist % 2] < dist:
        
        continue
    
    for u,w in graph[v]:
        
        cost = dist + w
            
        if distance[u][cost % 2] > cost:

            distance[u][cost % 2] = cost
            heapq.heappush(queue,(cost,u))


for i in range(1,n+1):
    
    if distance[i][0] == INF and distance[i][1] == INF:
        
        print(-1,-1)
    
    elif distance[i][0] == INF and distance[i][1] != INF:
        
        print(distance[i][1],-1)
    
    elif distance[i][0] != INF and distance[i][1] == INF:
        
        print(-1,distance[i][0])
    
    else:
        
        print(distance[i][1],distance[i][0])