[백준 알고리즘] 9370번: 미확인 도착지 (Python)

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

9370번: 미확인 도착지

소스코드

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

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

  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,[cur_dis+next_dis,next_node])

  return min_dis

t = int(input())
for _ in range(t):
  n,m,t = map(int,input().split())
  s,g,h = map(int,input().split())
  graph = [[] for _ in range(n+1)]
  ans = []
  destination = []
  for _ in range(m):
    a,b,d = map(int,input().split())
    graph[a].append([b,d])
    graph[b].append([a,d])

  s_to = dijkstra(s)
  g_to = dijkstra(g)
  h_to = dijkstra(h)
  
  for _ in range(t):
    x = int(input())
    if (s_to[g] + g_to[h] +h_to[x] == s_to[x]) or (s_to[h] + h_to[g] + g_to[x] == s_to[x]):
      ans.append(x)
  
  print(*sorted(ans))

 

풀이

★ 백준 1504번 문제인 특정한 최단 경로 문제와 비슷한 유형이었던 거 같습니다. 

 

★ 정점 g와 h사이에 있는 교차로를 통과하여 목적지로 갈 수 있는지 여부를 확인해야 하기 때문에 출발점이 s -> g - > h -> t로 가는 경로와 s -> h -> g -> t로 갈 수 있는 경로 두가지를 확인해주면 됩니다 ! 

 

★ 이때 최단 경로를 찾는 배열을 float('inf')로 초기화하면 오답 판정을 받게 되는데 그 이유는 INF + INF = INF가 성립되기 때문입니다 :)