다익스트라 알고리즘 응용하기 - 특정 조건에 맞는 길이를 가진 최단 경로를 구하는 방법

1. 문제

 

8347번: Bug (acmicpc.net)

8347번: Bug

 

2. 풀이

 

목적지까지 최단경로를 구해야하는데

 

문제는 홀수길이를 가지는 최단 경로를 구해야한다

 

 

그냥 사용하면 2를 답을 내는데.. 문제에서 원하는건 7로 가는 경로이다

 

 

쉬운 문제인데 이게 생각하기가 힘드네

 

너무 오랜만에 다익스트라 사용해서 그런가

 

어떻게 하냐면.. distance를 2차원으로 만들면 된다

 

짝수 최단경로 길이를 가지는 칸과 홀수 최단 경로 길이를 가지는 칸

 

그래서 다익스트라 알고리즘을 사용하는 중에, 길이가 짝수이면 짝수인 칸에 저장하고

 

홀수이면 홀수인 칸에 저장하도록 하면 된다

 

import heapq
from sys import stdin

INF = 100000000000000000000000000000

def dijkstra(start,n):
    
    q = []

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

    distance[start][0] = 0
    distance[start][1] = 0

    heapq.heappush(q,(0,start))

    while q:
        
        dist,v = heapq.heappop(q)
    
        if distance[v][dist%2] < dist:

             continue

        for b,c in graph[v]:

            cost = dist + c

            if distance[b][cost%2] > cost:

                distance[b][cost%2] = cost
                heapq.heappush(q,(cost,b))
    
    return distance

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

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

for _ in range(m):
    
    a,b,c = map(int,stdin.readline().split())

    graph[a].append((b,c))
    graph[b].append((a,c))

distance = dijkstra(1,n)

if distance[n][1] == INF:
    
    print(0)

else:
    
    print(distance[n][1])