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

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

import heapq

import sys

input = sys . stdin . readline

INF = int ( 1e9 ) # 무한을 의미

n , m = map ( int , input (). split ()) # 노드,간선

graph =[[ ] for _ in range ( n + 1 )] # 노드와 각노드의 연걸정보를 담은 리스트

# 모든 간선의 정보 입력 받기

for _ in range ( m ):

a , b , c = map ( int , input (). split ()) # a에서 b로가는 비용이 c

graph [ a ]. append (( b , c ))

graph [ b ]. append (( a , c ))

v_1 , v_2 = map ( int , input (). split ())

def dijkstra ( start ):

d =[ INF ]*( n + 1 )

q =[ ]

# 시작 노드, 자기자신으로 가는 최단거리는 0, 큐에 삽입

heapq . heappush ( q ,( 0 , start ))

d [ start ]= 0

while q : # q가 빌때까지 반복수행

dist , now = heapq . heappop ( q ) # 최단거리의 거리와, 노드 정보 추출

if d [ now ]< dist : # 현재 노드가 처리된적 있다면 무시

continue

for i in graph [ now ]: # 현재 노드와 연결된 노드들도 확인

cost = dist + i [ 1 ]

if cost < d [ i [ 0 ]]: # now 노드를 거쳐가는 것이 최단거리일 경우

d [ i [ 0 ]]= cost

heapq . heappush ( q ,( cost , i [ 0 ]))

return d

d = dijkstra ( 1 ) # 다익스트라 알고리즘 수행

d_1 = dijkstra ( v_1 )

d_2 = dijkstra ( v_2 )

a = d [ v_1 ]+ d_1 [ v_2 ]+ d_2 [ n ]

b = d [ v_2 ]+ d_2 [ v_1 ]+ d_1 [ n ]

if min ( a , b )>= INF :

print (- 1 )

else :

from http://20210916start.tistory.com/56 by ccl(A) rewrite - 2021-09-23 23:00:22