파이썬 백준 1504번 : 특정한 최단경로

제목

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

 

 

풀이

알고리즘 : 다익스트라

자료구조 : 인접리스트,  최소힙

 

import sys
import heapq

def dijkstra(s,e): #다익스트라 알고리즘
    heap=[]
    heapq.heappush(heap,s) #힙에 시작노드 넣기 
    dist[s]=0
    visited.add(s) #방문처리
    while heap:
        v1=heapq.heappop(heap) 
        for node in Graph[v1]: #연결된 노드 들 중방문되지 않았고 기존거리보다 거쳐서가는거리가 더 작은경우 dist갱신    
            if node[0] is not visited and dist[node[0]]>dist[v1]+node[1]:
                dist[node[0]]=dist[v1]+node[1]
                heapq.heappush(heap,node[0])
                visited.add(node[0]) #방문처리

    return dist[e] #e 까지 가는거리 return  



N,E=map(int,sys.stdin.readline().split())
Graph=[[] for _ in range(N+1)]
visited=set()
for _ in range(E): # 인접리스트 생성
    v1,v2,w=map(int,sys.stdin.readline().split())
    Graph[v1].append((v2,w))
    Graph[v2].append((v1, w))
V1,V2=map(int,sys.stdin.readline().split())

result1=result2=0
result1_list=[1,V1,V2,N] #case1 V1->V2 순서로 방문
result2_list=[1,V2,V1,N] #case2 V2->V1 순서로 방문
for i in range(len(result1_list)-1):
    dist=[100000000]*(N+1)
    result1+=dijkstra(result1_list[i],result1_list[i+1])
for i in range(len(result2_list)-1):
    dist=[100000000]*(N+1)
    result2+=dijkstra(result2_list[i],result2_list[i+1])

if result1>=100000000 and result2>=100000000: # 경로가 없는 경우
    print(-1)
else:
    print(min(result1,result2))