[백준]13911 집구하기 다익스트라

문제풀이

스벅까지의 거리와 맥날까지의 거리의 합이 최소가 되는 곳을 구하면 된다.

스벅, 맥날은 하나 이상이 있다. 따라서 각각의 집에서 그 집과 가장 가까운 스벅, 맥날까지의 거리를 구하고 그 합이 최소가 되는 집을 찾으면 된다.

도로는 양방향이고 노드사이의 서로 다른 양의 가중치가 존재하므로 다익스트라를 이용하면 된다. 

이때 각각의 집에서 가장 가까운 스벅, 맥날까지의 거리만 구하면 된다.  따라서 아래와 같은 순서로 진행한다.

 

0. 예제

 

 

 

1. 모든 맥날과 가중치 0으로 이은 맥날NODE, 모든 스벅과 가중치 0으로 이은 스벅NODE를 만든다.

 

 

 

2. 맥날NODE에서 각 집까지의 거리, 스벅NODE에서 각 집까지의 거리를 구한다.

 

 

 

주의할점

모든 맥날점과 모든 스벅점을 0의 가중치로 이어서 만든 맥날NODE와 스벅NODE는 가상의 노드이다. 따라서 최단거리를 찾을때 해당 노드들을 이용하면 안된다. (마치 없는 지름길을 이용하는 꼴이된다.)

예를 들어 스벅NODE에서 각 노드까지의 거리를 구한다고 가정하자

5번노드까지 가는데 실제로는 최단거리가 경로(8-6-4-2)로서 7이 되어야 한다.

 

 

하지만 맥날NODE를 이용하는 경로(8-6-4-1-맥날NODE-5)로 가면 6이 된다.

 

 

 

따라서 최단거리를 구할 때 가상의 노드(맥날NODE, 스벅NODE)를 이용하지 않게 하기위해 아래의 코드를 다익스트라 알고리즘에 추가한다.

        for toNode,toD in graph[node]:
            # 맥날이나 스벅이면 x
            if toNode==V+1 or toNode==V+2:
                continue

 

소스코드

import heapq
import sys

INF=9876543210
V,E=map(int,input().split())
L=[]
graph={}
for i in range(1,V+1):
    graph[i]=[]
mLoc=V+1
sLoc=V+2
graph[mLoc]=[]
graph[sLoc]=[]

for i in range(E):
    a,b,d=map(int,sys.stdin.readline().split())
    graph[a].append([b,d])
    graph[b].append([a,d])

M,x=map(int,input().split())
mL=list(map(int,input().split()))

S,y=map(int,input().split())
sL=list(map(int,input().split()))

for m in mL:
    graph[mLoc].append([m,0])
    graph[m].append([mLoc,0])
for s in sL:
    graph[sLoc].append([s,0])
    graph[s].append([sLoc,0])

mNodeDist=[INF for i in range(V+3)]
mNodeDist[V+1]=0

sNodeDist=[INF for i in range(V+3)]
sNodeDist[V+2]=0

def dijstra(start,nodeDist):
    dij=[[0,start]]
    while(dij):
        d,node=heapq.heappop(dij)
        if nodeDist[node]<d:
            continue

        for toNode,toD in graph[node]:
            # 맥날이나 스벅이면 x
            if toNode==V+1 or toNode==V+2:
                continue
            addedD=toD+d
            if addedD<nodeDist[toNode]:
                nodeDist[toNode]=addedD
                heapq.heappush(dij,[addedD,toNode])

dijstra(V+1,mNodeDist)
dijstra(V+2,sNodeDist)

# print(mNodeDist[1:V+1])
# print(sNodeDist[1:V+1])

ans=INF
for i in range(1,V+1):
    if (i in mL) or (i in sL):
        continue
    if mNodeDist[i]<=x and sNodeDist[i]<=y:
        if mNodeDist[i]+sNodeDist[i]<ans:
            ans=mNodeDist[i]+sNodeDist[i]

if ans==INF:
    print(-1)
else:
    print(ans)