야쿠르트 아줌마 야쿠르트 주세요(백준 20160)

다익스트라 알고리즘으로 매번 최단 경로를 계산해서 요구르트를 살 수 있는 지 확인한다. 

import sys 
import heapq 
input = sys.stdin.readline 
inf = int(1e9)
n,m = map(int, input().split())
gra = [[]for _ in range(n+1)]
for _ in range(m):
    a,b,c = map(int, input().split())
    gra[a].append((b,c))
    gra[b].append((a,c))
yogu = list(map(int, input().split()))
start = int(input())

def dijk(start):
    dist = [inf for _ in range(n+1)]
    dist[start] = 0 
    q = []
    q.append((0,start))
    heapq.heapify(q)
    while q :
        wei, now = heapq.heappop(q)
        if dist[now]< wei : 
            continue
        
        for nextnode,nextcost in gra[now]:
            if dist[nextnode] > wei+ nextcost:
                dist[nextnode]  = wei+nextcost
                heapq.heappush(q, (dist[nextnode], nextnode))
    return dist 

ans = inf 
total = 0 
firstsell = yogu[0]
firstarr = dijk(start)
for point in yogu :
    distances = dijk(firstsell)
    distance = distances[point] 
    if distance ==inf :
        continue
    total += distance 
    firstsell = point 
    mydist = firstarr[point] 
    if total >= mydist :
        ans = min(ans, point)
if ans== inf :
    print(-1)
else:
    print(ans)