[백준] 9370번 : 미확인 도착지 [파이썬]

[백준] 9370번 : 미확인 도착지 [파이썬]

import heapq

INF = int ( 1e9 )

c = int ( input ()) # 테스트 케이스

def dij ( start ):

distance =[ INF ]*( n + 1 )

q =[]

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

distance [ start ]= 0

while q :

dist , now = heapq . heappop ( q )

if distance [ now ]< dist :

continue

for i in graph [ now ]:

cost = dist + i [ 1 ]

if cost < distance [ i [ 0 ]]:

distance [ i [ 0 ]]= cost

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

return distance

for _ in range ( c ):

n , m , t = map ( int , input (). split ()) # 노드, 간선,목적지 후보의갯수

s , g , h = map ( int , input (). split ()) # target의 출발,g,h

graph =[[] for _ in range ( n + 1 )]

for _ in range ( m ):

a , b , d = map ( int , input (). split ()) # 노드간의 연결정보

graph [ a ]. append (( b , d )) # 양방향이므로 둘다 입력

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

target =[] # 목적지 후보를 담을 리스트

for _ in range ( t ): #목적지 후보 입력

x = int ( input ())

target . append ( x )

target . sort () # 오름 차순으로 정렬

dist_1 = dij ( s )

dist_g = dij ( g )

dist_h = dij ( h )

for i in target :

a = dist_1 [ g ]+ dist_g [ h ]+ dist_h [ i ]

b = dist_1 [ h ]+ dist_h [ g ]+ dist_g [ i ]

if min ( a , b )== dist_1 [ i ]:

print ( i , end = ' ' )

from http://20210916start.tistory.com/69 by ccl(A) rewrite - 2021-09-24 09:00:42