[백준/Python] 1504: 특정한 최단 경로

문제

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

1504번: 특정한 최단 경로

---

풀이

 

일반적인 다익스트라 문제와 비슷하다.

dijkstra() 부분은 큰 차이점이 없다.

양방향이므로 graph에 양쪽 모두 추가해주고, 이 부분을 주의해야한다.

d1 = dijkstra(1)
d2 = dijkstra(v1)
d3 = dijkstra(v2)
res = min(d1[v1]+d2[v2]+d3[N], d1[v2]+d3[v1]+d2[N])

d1=1에서 시작

d2=v1에서 시작

d3=v2에서 시작

d1[v1] =1에서 시작해서 v1까지 가는 경로

 

 길은 v1-v2-n or v2-v1-n 이고, 구하는 값은 두가지 중 최솟값이므로 res를 구하면 된다.

---

 

코드

import heapq
import sys
INF = sys.maxsize
input = sys.stdin.readline

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

N, E = map(int, input().split())
graph = [[] for _ in range(N+1)]
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())
d1 = dijkstra(1)
d2 = dijkstra(v1)
d3 = dijkstra(v2)
res = min(d1[v1]+d2[v2]+d3[N], d1[v2]+d3[v1]+d2[N])
print(res if res < INF else -1)