문제

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

코드

import heapq
import sys
n,e=map(int,input().split())
graph={}
for i in range(1,n+1):
    graph[i]={}

for i in range(e):
    a,b,c=map(int,input().split())
    graph[a][b]=c
    graph[b][a]=c

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


def dij(s):
    mnum = sys.maxsize
    dis= [mnum] * (n + 1)
    dis[s]=0
    q=[]
    heapq.heappush(q,[dis[s],s])
    while q:
        now_dis,now=heapq.heappop(q)
        if now_dis>dis[now]:
            continue
        for destination,w in graph[now].items():
            if dis[destination]>w+now_dis:
                dis[destination]=w+now_dis
                heapq.heappush(q,[w+now_dis,destination])
    return dis
one=dij(1)
ver1=dij(v1)
ver2=dij(v2)
inf=sys.maxsize
cnt=min(one[v1]+ver1[v2]+ver2[n],one[v2]+ver2[v1]+ver1[n])
print(cnt if cnt<inf else -1)

• 다익스트라 최단경로 문제이다.

• 경우의 수:
  1->v1->v2->n or 1->v2->v1->n이므로 둘 중의 최소값으로 해주어야한다.

• 이를 위해 시작이 1일때 v1 일때 v2일때 총 세번의 다익스트라를 실행하고 그 결과값을 반환하여 cnt=min(one[v1]+ver1[v2]+ver2[n],one[v2]+ver2[v1]+ver1[n]) 둘중 작은값으로 결정한다.

• else -1은 경로가 없을 경우이다.