[백준] 1504번-(Python 파이썬) - Dijkstra
문제링크 : https://www.acmicpc.net/problem/1504
이번 문제는 방향성이 없는 그래프에서 두개의 정점을 지날 때의 최단 거리를 구하는 문제이다.
v1, v2 두 정점을 지나서 n번 정점으로 가야하는데 처음에 무조건 순서대로 v1을 지나고 v2를 지나야 하는 줄 알고 문제를 제출하여 왜 틀렸었는지 몰라 계속하여 고민하였다.
두 개의 정점을 지나야 한다는 것만 해결하면 다익스트라 알고리즘을 이용해 금방 해결할 수 있다.
링크텍스트
백준(1916번)-최소비용 구하기(다익스트라 알고리즘) 링크에 설명해두었으니 참고하면 이해하기에 편할것이다.
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
inf = sys.maxsize
n, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]
dp_1 = [inf] * (n + 1)
dp_2 = [inf] * (n + 1)
dp_3 = [inf] * (n + 1)
def dijkstra(start, dp):
heap = []
heappush(heap, [0, start])
dp[start] = 0
while heap:
w, n = heappop(heap)
for n_n, wei in graph[n]:
n_w = wei + w
if n_w < dp[n_n]:
dp[n_n] = n_w
heappush(heap, [n_w, n_n])
for _ in range(e):
a, b, c = map(int, input().split())
graph[a].append([b, c])
graph[b].append([a, c])
v1, v2 = map(int, input().split())
dijkstra(1, dp_1)
dijkstra(v1, dp_2)
dijkstra(v2, dp_3)
min_ = min(dp_1[v1] + dp_2[v2] + dp_3[n], dp_1[v2] + dp_2[n] + dp_3[v1])
if min_ >= inf:
print(-1)
else:
print(min_)
Author And Source
이 문제에 관하여([백준] 1504번-(Python 파이썬) - Dijkstra), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hamfan524/백준-1504번-Python-파이썬-Dijkstra저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)