[BOJ][Python]1504 풀이

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

1504번: 특정한 최단 경로

import heapq
import sys
ssr = sys.stdin.readline

INF = 200000001

def dijkstra(start, end):
    h = [(0, start)]
    min_dist = [INF for _ in range(n+1)]
    min_dist[start] = 0
    while h:
        cur_dist, cur_node = heapq.heappop(h)
        if cur_dist > min_dist[cur_node]:
            continue
        for next_dist, next_node in edges[cur_node]:
            if min_dist[cur_node]+next_dist < min_dist[next_node]:
                min_dist[next_node] = min_dist[cur_node]+next_dist
                heapq.heappush(h, (min_dist[next_node], next_node))
    return min_dist[end]
        
def sol(v1, v2):
    ans = min(dijkstra(1, v1)+dijkstra(v1, v2)+dijkstra(v2, n), dijkstra(1, v2)+dijkstra(v2, v1)+dijkstra(v1, n))
    print(ans if ans< INF else -1)
    
n, e = map(int, ssr().split())
edges = [[] for _ in range(n+1)]
for _ in range(e):
    a, b, c = map(int, ssr().split())
    edges[a].append((c, b))
    edges[b].append((c, a))
v1, v2 = map(int, ssr().split())
sol(v1, v2)

약간 조심하면 되는 문제입니다. 입력으로 주어지는 간선이 방향이 없기 때문에 인접리스트에 저장을 할 경우 출발지와 도착지를 바꿔서 한 번 더 저장해주어야합니다. 그리고 경로의 순서가 무조건 1 → v1 → v2 → n 이 아니므로 답은 1 → v1 → v2 → n 또는 1 → v2 → v1 → n 중 더 작은 값을 출력하면 됩니다.

 

문제 자체가 어렵지는 않지만 조금 세심하게 조건을 생각해볼 필요가 있는 문제였던 것 같습니다.

 

데이크스트라에 대해 정리한 글을 업로드했습니다. 데이크스트라가 더 궁금하신 분들은 읽어보셔도 좋다고 생각해요.

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드