백준 13911 <집 구하기> Python

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

---

다익스트라 알고리즘 문제입니다.

시작점과 끝점을 어떻게 잡을지 고민일텐데 사실 크게 상관은 없습니다. 어느 경우든 두 번으로 구할 수 있습니다.

 

1. 집이 될 수 있는 위치 ~ 가게

해당 경우는 집이 될 수 있는 모든 위치를 동시에 시작점으로 잡고 두 가게를 각각 다익스트라 알고리즘을 돌리면 됩니다.

 

2. 가게 ~ 집이될 수 있는 위치

해당 경우는 역시 알고리즘을 두 번 돌릴텐데 각 가게마다 위치를 동시에 시작점으로 잡고 나머지 위치를 대상으로 다익스트라 알고리즘을 진행하면 됩니다.

 

결국 해당 문제의 핵심은 시작점마다 각각 알고리즘을 돌리는 것이 아닌 모든 지점을 시작점으로 알고리즘을 돌릴 수 있는가에 대한 것 같습니다. 

---

import sys
import heapq as hq

input = sys.stdin.readline


# 다익스트라
def dijkstra(graph, stores):
    # 큐
    q = [[0, store] for store in stores]
    # 최단거리 리스트
    min_dists = [float('inf') for _ in range(len(graph))]
    for store in stores:
        min_dists[store] = 0

    # 순회
    while q:
        # 거리 / 노드
        now_dist, now_node = hq.heappop(q)
        # 현재 거리가 현재 노드의 최단거리보다 길면 패스
        if now_dist > min_dists[now_node]:
            continue

        # 이동 가능 노드 탐색
        for next_node, dist in graph[now_node]:
            # 다음 거리
            next_dist = now_dist + dist
            # 다음 거리가 다음 노드의 최단거리보다 짧을때만
            if next_dist < min_dists[next_node]:
                # 큐에 추가
                hq.heappush(q, [next_dist, next_node])
                # 최단거리 갱신
                min_dists[next_node] = next_dist
    
    return min_dists


def solution(V, E, edges, M, x, Ms, S, y, Ss):
    # 그래프
    graph = [[] for _ in range(V+1)]
    for u, v, w in edges:
        graph[u].append([v, w])
        graph[v].append([u, w])
    
    # 모든 가게부터 가게가 없는 위치까지의 거리 구하기
    M_dists = dijkstra(graph, Ms)
    S_dists = dijkstra(graph, Ss)
    # 조건에 맞는 노드 찾기
    min_dist = float('inf')
    for m, s in zip(M_dists, S_dists):
        # 가게 위치가 아니고 범위 안에 있으면
        if (m and m <= x) and (s and s <= y):
            # 최단거리 갱신
            min_dist = min(min_dist, m+s)

    print(min_dist if min_dist != float('inf') else -1)


# 입력
V, E = map(int, input().strip().split())
edges = [list(map(int, input().strip().split())) for _ in range(E)]
M, x = map(int, input().strip().split())
Ms = list(map(int, input().strip().split()))
S, y = map(int, input().strip().split())
Ss = list(map(int, input().strip().split()))

solution(V, E, edges, M, x, Ms, S, y, Ss)