[백준] 1504번 특정한 최단 경로 - 파이썬

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

1504번: 특정한 최단 경로

 

풀이

1, 양방향이고 최대치를 sys.maxsize로 잡아서 문제의 제한사항으로부터 자유로워 졌다.

2, 똑같은 다익스트라문제이지만 무조건 마지막에 주어진 두 정점을 지나야하기때문에 시작값이 매개변수로 주어진 다익스트라 함수를 만들어서 경로 1 - num1 - num2 - n 이랑 1 - num2 - num1 - n을 비교해준다.

# 1504번 특정한 최단 경로
# 다익스트라 + 완전탐색
import sys
import heapq
input = sys.stdin.readline

INF = sys.maxsize

def dijkstra(start):
    distance = [INF] * (n+1)
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            continue
        for v, w in graph[now]:
            cost = dist + w
            if cost < distance[v]:
                distance[v] = cost
                heapq.heappush(q, (cost, v))
    return distance

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
num1, num2 = map(int, input().split())

# 무조건 거쳐야 하는 정점이기에 
# 경로 2개가 있다. 1 - num1 - num2 - n 이랑 1 - num2 - num1 - n 
# 둘의 최단거리 비교 만일 도착점을 거치지 못했다면 둘의 최단경로 값은 INF를 한참 넘어서는 값이 될것이다.
first = dijkstra(1)
n_num1 = dijkstra(num1)
n_num2 = dijkstra(num2)

check = min(first[num1] + n_num1[num2] + n_num2[n], first[num2] + n_num2[num1] + n_num1[n])
if check < INF:
    print(check)
else:
    print(-1)

출력결과