[BOJ] 13911 - 집 구하기 (Python)

 

 

아이디어

 

데이크스트라 알고리즘으로 맥도날드와 스타벅스로부터 집까지의 최단거리를 각각 구하고 그 합의 최솟값을 구한다.

 

 

풀이

 

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

INF = int(1e8)

def solution():

    def dijkstra(stores, limit):
        heap = []
        D = [INF]*(V+1)
        for i in stores:
            heap.append((0, i))
            D[i] = 0
        while heap:
            w, u = heappop(heap)
            if w >= limit:
                continue
            for v, _w in graph[u]:
                total = w+_w
                if total < D[v]:
                    D[v] = total
                    heappush(heap, (total, v))
        return D

    V, E = map(int, input().split())
    graph = [[] for _ in range(V+1)]
    for _ in range(E):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
        graph[v].append((u, w))
    M, x = map(int, input().split())
    mcdonalds = tuple(map(int, input().split()))
    S, y = map(int, input().split())
    starbucks = tuple(map(int, input().split()))
    D1 = dijkstra(mcdonalds, x)
    D2 = dijkstra(starbucks, y)
    res = -1
    for i in range(1, V+1):
        if 0 < D1[i] <= x and 0 < D2[i] <= y:
            if D1[i]+D2[i] < res or res < 0:
                res = D1[i]+D2[i]
    print(res)

solution()