[백준 1504] 특정한 최단 경로 - python (solved.ac - 골드 4)

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

1504번: 특정한 최단 경로

풀이

문제를 보았을때 알수있는 힌트

1. 방향성이 없음(양쪽을 다 갈수있음)

2. 1에서 n까지의 최단 거리를 알고싶어함.

3. 이동간의 거리가 존재한다.

4. 정해진 2곳을 지나가야한다.

1과 3번을 통해서 다익스트라 알고리즘을 이용하면 된다는 것을 알수있다. 4번을 통해서 다익스트라를 2번더 반복해서 최소 거리를 찾으면 해결되는 문제이다.

기본 다익스트라 한번만 사용하는 문제를 조금 응용한 정도의 문제인듯하다.

 

import sys
import heapq

INF = 1e9
input= sys.stdin.readline

n,e= map(int,input().split())

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

for i in range(e):
    x,y,z = map(int,input().split())
    graph[x].append((y,z))
    graph[y].append((x,z))

v1,v2= map(int,input().split())

start_list=[1,v1,v2]
result=[]
for start in start_list:
    q =[]
    graph_distance=[INF for _ in range(n+1)]
    heapq.heappush(q,(0,start))
    graph_distance[start]= 0

    while q:
        v= heapq.heappop(q)
        if graph_distance[v[1]]< v[0]:
            continue
        for i in graph[v[1]]:
            cost = graph_distance[v[1]]+i[1]
            if cost<graph_distance[i[0]]:
                graph_distance[i[0]]=cost
                heapq.heappush(q,(cost,i[0]))
    result.append(graph_distance)

answer = min(result[0][v1]+result[1][v2]+result[2][n],
            result[0][v2]+result[2][v1]+result[1][n])
if answer >= INF:
    print(-1)
else:
    print(answer)

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon1504.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리