[Python]최단경로 백준 1504

   문제

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

다익스트라를 여러번 이용해 찾는 문제이다.

양방향이라는 점에 주의 하여야 입력을 받아야 하고 반드시 거쳐야하는 두점중 하나가

 N번 정점일수 있다는 것도 생각해야한다.

이 두가지 를 고려하지 않아 몇번 틀렸다.

import sys
import heapq
INF=sys.maxsize
 
def Dijkstra(start):
    q=[]
    heapq.heappush(q,[0,start])
    result=[INF for _ in range(V+1)]
    result[start]=0#둘중하나가 도착점일 경우를 생각해서 자신으로 가는값을 0으로 초기화해준다.
    while q:
        dis,s=heapq.heappop(q)
        if dis>result[s]:#이전값보다 거리가 크다면 넘어간다.
            continue
        for d,x in G[s]:#
            d+=dis
            if d<result[x]:
                result[x]=d
                heapq.heappush(q,[d,x])
    return result
 
 
V,E=map(int,sys.stdin.readline().split())#노드 간선
 
G=[[] for _ in range(V+1)]#그래프
for _ in range(E):#양방향 저장
    start,end,distance=map(int,sys.stdin.readline().split())
    G[start].append([distance,end])
    G[end].append([distance,start])
 
 
 
D1,D2=map(int,sys.stdin.readline().split())
 
 
dis1=Dijkstra(1)#1->D1 1->D2
dis2=Dijkstra(D1)#D1->D2 D1->N
result1=dis1[D1]+dis2[D2]+Dijkstra(D2)[V]#1->D1->D2->N
result2=dis1[D2]+dis2[D2]+dis2[V]#1->D2->D1->N
 
if result2>=INF and result1>=INF:
    print(-1)
else:
    print(min(result1,result2))