✍ 문제

문제링크: https://www.acmicpc.net/problem/1504

👏 풀이과정

이 문제는 dijkstra 알고리즘을 사용하는 문제이다. i -> v1 -> v2 -> N or i ->v2 ->v1 ->N 중에 작은값을 출력하면 된다. 만약 처음 정의해준 초기값보다 크게 나오면 -1 을 출력하면 된다

import sys
import heapq

def dijkstra(start):
    distance = [int(1e9)] * (N + 1)
    distance[start] = 0
    queue =[]
    heapq.heappush(queue,(0,start))

    while len(queue) != 0:
        cost,pre = heapq.heappop(queue)
        if distance[pre] < cost:
            continue
        for en,co in array[pre]:
            if distance[en] > co +cost:
                distance[en] = co + cost
                heapq.heappush(queue,((co+cost),en))
    return distance

N, E = map(int,sys.stdin.readline().split())

array = [[] for _ in range(N+1)]

for _ in range(E):
    st,en,co = map(int,sys.stdin.readline().split())

    array[st].append((en,co))
    array[en].append((st,co))

v1,v2 = map(int,sys.stdin.readline().split())


dis_1 = dijkstra(1)
dis_2 = dijkstra(v1)
dis_3 = dijkstra(v2)


answer = min(dis_1[v1] + dis_2[v2] +dis_3[N],dis_1[v2]+dis_3[v1]+dis_2[N])

if answer >= 1e9:
    print(-1)
else:
    print(answer)