[BOJ 20160, Python 3] 야구르트 아줌마 야구르트 주세요

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

20160번: 야쿠르트 아줌마 야쿠르트 주세요

 

 

풀이

문제를 보면 모든 정점에서 다익스트라 알고리즘을 돌려야할 것 같지만, 야구르트 아줌마가 첫번째 지점을 제외한 야구르트를 파는 나머지 9개 지점의 정점을 다익스트라로 돌리고, 내가 시작점에서 움직이는 다익스트라를 돌려 총 10번 다익스트라를 돌리면 됩니다.

혹은 야구르트 아줌마 정점 9개를 돌리면서 내가 시작점에서 움직이는 다익스트라도 같이 돌려 총 18번 다익스트라를 돌려도 시간내에 통과합니다.

 

 

코드

아래 코드는 다익스트라를 총 18번 돌리는 코드입니다.

def dijkstra(s, e):
    q = []; heappush(q, [0, s])
    S = [float('inf')] * (n+1)
    S[s] = 0
    while q:
        t, x = heappop(q)
        if t > S[x]: continue
        for nx, nt in adj[x]:
            if S[nx] > t + nt:
                S[nx] = t + nt
                heappush(q, [t + nt, nx])
    return S[e]
 
from heapq import *
input = __import__('sys').stdin.readline
 
n, e = map(int, input().split())
adj = [[] for _ in range(n+1)]
for i in range(e):
    u, v, w = map(int, input().split())
    adj[u].append([v, w])
    adj[v].append([u, w])
arr = [*map(int, input().split())]
s = int(input())
 
ans = float('inf')
female = 0
prev = arr[0]
for i in range(10):
    fval = dijkstra(prev, arr[i])
    if fval == float('inf'): continue
    female += fval
    prev = arr[i]
    mval = dijkstra(s, arr[i])
    if female >= mval: ans = min(ans, arr[i])
print([-1, ans][ans != float('inf')])