[Python] 백준 1504 특정한 최단 경로 | 다익스트라

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

 

문제 해결 포인트

- v1 -> v2 순서 또는 v2 -> v1 순서 각각의 거리를 구하여 작은 값을 출력한다. (2번의 다익스트라)

- 경로가 없는 경우(결과 값이 INF보다 크거나 같은 경우) -1을 출력

 

자세한 내용은 코드 주석 참고

 

 

작성 코드

 

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

N, E = map(int, input().split())  # 노드수, 간선수
graph = [[] for _ in range(N+1)]  # 인접 리스트

distance2 = [INF]*(N+1)  # v1에서 각 노드 최소 거리 저장
distance3 = [INF]*(N+1)  # v2에서 각 노드 최소 거리 저장

for _ in range(E):  # 인접 리스트(무방향)
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
    graph[b].append((a, w))
    
v1, v2 = map(int, input().split())  # 반드시 지나야 할 두 노드

def dijkstra(start, distance):  # 다익스트라
    q = []
    distance[start] = 0
    heapq.heappush(q, (0, start))  # 우선 순위 큐 초기화

    while q:  # 큐에 값이 있을 때
        dist, now = heapq.heappop(q)  # 거리가 최소인 노드
        if distance[now] < dist:  # 방문한 노드
            continue
        for v, w in graph[now]:
            cost = dist + w
            if distance[v] > cost:
                distance[v] = cost
                heapq.heappush(q, (cost, v))


dijkstra(v1, distance2)  # v1으로 부터 최소 거리 구하기(distance2)
dijkstra(v2, distance3)  # v2로 부터 최소 거리 구하기(distance3)

# distance2는 v1의 distance3는 v3의 최소 거리이다. 
# 1 -> v1 -> v2 -> N 또는 1 -> v2 -> v1 -> N 중 작은 값을 구한다.
result = min(distance2[1] + distance3[N] + distance2[v2], distance3[1] + distance2[N] + distance3[v1])

print(-1 if result >= INF else result)  # 길이 없다면(INF보다 크거나 같다면) -1 반환

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚