[파이썬] 백준 13911 : 집 구하기 (골드2)

[파이썬] 백준 13911 : 집 구하기 (골드2)

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

 

---

풀이

방향성 생각

• 다익스트라
• 맥도날드 따로, 스타벅스 따로 다익스트라를 돌린다.

---

전체코드

from collections import defaultdict as dd
import heapq as hq
import sys

input = lambda : sys.stdin.readline().rstrip()
INF = float('inf')

N,M = map(int,input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost))
    G[b].append((a,cost))

mac,x = map(int,input().split())
mac_set = set(map(int, input().split()))
star,y = map(int,input().split())
star_set = set(map(int,input().split()))

def di(G,locs):
    V = [INF]*(N+1)
    heap = []

    for loc in locs:
        V[loc] = 0
        hq.heappush(heap,(0,loc))

    while heap:
        t,x = hq.heappop(heap)
        if t > V[x]:
            continue
        for nx,cost in G[x]:
            nt = t + cost
            if nt < V[nx]:
                V[nx] = nt
                hq.heappush(heap,(nt,nx))
    return V

max_dist = di(G,mac_set)
star_dist = di(G,star_set)

house = set(range(1,N+1)) - (mac_set|star_set)
answer = INF
for h in house:
    if max_dist[h]<= x and star_dist[h]<=y:
        answer = min(answer, max_dist[h] + star_dist[h])
print(answer if answer != INF else -1)

---

코멘트

• 입력 중복간선 처리한다고, defaultdict이나 중복순회하면 느리게 나온다.
• 그냥 다익스트라에서 if t > V[x]: 이거로 필터링하는게 나은듯