✅ BOJ 1504 - 다익스트라 응용

다익스트라

백준 1504번: 특정한 최단경로

ALGORITHM

다익스트라 사용함

PROBLEM

시작점 1에서 끝점 N까지 감
v1, v2 두 정점 반드시 지나야 함
순서는 자유, 간선 재사용 가능
항상 최단경로여야 함

APPROACH

다익스트라 총 3번 돌림
1 → v1 → v2 → N
1 → v2 → v1 → N
두 경로 계산해서 더 짧은 쪽 씀

다익스트라는 시작노드 하나에서 모든 노드까지 거리 배열 만들고
필요한 구간만 꺼내서 더함
목표노드는 함수 안에서 안 씀

IMPLEMENTATION

그래프는 (가중치, 다음노드) 형태로 저장
heapq에 (누적가중치, 노드)로 넣고 최소거리 갱신
시작노드 바뀌면 힙과 거리배열 새로 만듦
경로 없으면 INF 남음 → -1 출력

SUMMARY

경로 출력 안 함, 가중치만 필요
다익스트라 3번, 두 케이스 비교로 끝냄

 

#dijkstra,shortest_path
import sys,heapq
input=sys.stdin.readline

def dijkstra(start,n,graph):
    heap=[]
    heapq.heappush(heap,(0,start)) #(가중치,시작노드)
    INF=float('inf')
    distance=[INF]*(n+1)
    distance[start]=0
    
    while heap:
        current_weight,current_node=heapq.heappop(heap)
        for next_weight,next_node in graph[current_node]:    
            accumulated_weight=current_weight+next_weight
            if accumulated_weight<distance[next_node]:
                distance[next_node]=accumulated_weight
                heapq.heappush(heap,(accumulated_weight,next_node))
    
    return distance

n,e=map(int,input().split())
graph=[[] for _ in range(n+1)]

for _ in range(e):
    start,end,weight=map(int,input().split())
    graph[start].append((weight,end))
    graph[end].append((weight,start))

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

distance_from_start=dijkstra(1,n,graph)
distance_from_v1=dijkstra(v1,n,graph)
distance_from_v2=dijkstra(v2,n,graph)

#1->v1->v2->n
shortest_path1=distance_from_start[v1]+distance_from_v1[v2]+distance_from_v2[n]
#1->v2->v1->n
shortest_path2=distance_from_start[v2]+distance_from_v2[v1]+distance_from_v1[n]
shorest_path=min(shortest_path1,shortest_path2)
print(shorest_path if shorest_path<float('inf') else -1)