백준 1504: 특정한 최단 경로 (Python)

 

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

1504번: 특정한 최단 경로

 

 

반드시 통과해야만 하는 정점이 있기 때문에 

1 -> v1 -> v2 -> n

1 -> v2 -> v1 -> n

다익스트라를 세번(1번 출발, v1 출발, v2 출발) 돌려서 두 값 중에 최소값을 찾아주면 된다

 

처음에 실패해서 찾아보니까 값을 세번 더하기 때문에 무한값을 줄여주면 된다고 해서 줄였는데 (1e9 -> 1e8)

여전히 틀림,,,, 자세히 보니까 코드에 오타 있었다 ㅎ^^ 멍청ㅎ,,

 

import heapq
import sys
input = sys.stdin.readline
INF = int(1e8)

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

graph = [[] for i 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())

def dijkstra(start):
    distance = [INF] * (n + 1)
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]

            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

    return distance

d1 = dijkstra(1)
d2 = dijkstra(v1)
d3 = dijkstra(v2)

res = min(d1[v1] + d2[v2] + d3[n], d1[v2] + d3[v1] + d2[n])

if res >= INF:
    print(-1)
else:
    print(res)