[백준 알고리즘] 5944번: Apple Delivery (Python)

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

5944번: Apple Delivery

 

소스코드

import sys
import heapq as hq
input = sys.stdin.readline

def dijkstra(start):
  q = []
  min_dis = [int(1e9) for _ in range(p+1)]
  min_dis[start] = 0
  hq.heappush(q,[0,start])

  while q:
    cur_dis,cur_node = hq.heappop(q)

    if min_dis[cur_node] < cur_dis:
      continue

    for next_node,next_dis in graph[cur_node]:
      if min_dis[next_node] > next_dis + cur_dis:
        min_dis[next_node] = next_dis + cur_dis
        hq.heappush(q,[next_dis+cur_dis,next_node])

  return min_dis

c,p,pb,pa1,pa2 = map(int,input().split())
graph = [[] for _ in range(p+1)]
for _ in range(c):
  a,b,l = map(int,input().split())
  graph[a].append([b,l])
  graph[b].append([a,l])

from_pb = dijkstra(pb)
from_pa1 = dijkstra(pa1)
from_pa2 = dijkstra(pa2)

ans1 = from_pb[pa1] + from_pa1[pa2] # pb -> pa1 -> pa2로 가는 경로
ans2 = from_pb[pa2] + from_pa2[pa1] # pb -> pa2 -> pa1으로 가는 경로
result = min(ans1,ans2)
print(result)

 

풀이

★ pb라는 출발점에서 시작하여 pa1, pa2를 거치는 최단 경로를 찾아주면 됩니다. 이 때 목적지가 따로 없어서 헷갈릴 수도 있는데, pa2 or pa1에 도달하면 끝나기 때문에 이 둘을 각각의 케이스의 목적지로 생각해주면 됩니다. 

 

★ 두 정점을 거치는 방법은 2가지가 있습니다. 1. pb -> pa1 -> pa2.  2. pb -> pa2 -> pa1. 각각의 케이스를 구하기 위해 pb에서 출발하는 경우, pa1에서 하는 경우, pa2에서 하는 경우의 최단경로를 다익스트라로 만들어준 뒤, 그 합을 구해야 합니다 :)