[백준 9370번] 미확인 도착지 (Python3)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
from heapq import heappush,heappop
INF = 10**9

def DFS(n,now):
  if n in result:
    return
  if now==start:
    return
  for last in path[now]:
    if last==g and now==h or now==g and last==h:
      result.add(n)
      return
    DFS(n,last)

def Djikstra():
  DP = [INF]*(N+1)
  hq = []
  heappush(hq,(0,start,start))

  while hq:
    w,now,last = heappop(hq)
    if DP[now] < w:
      continue
    if DP[now] == w:
      path[now].add(last)
      continue
    DP[now] = w
    path[now] = {last}
    for next,w1 in graph[now]:
      heappush(hq,(w+w1,next,now))

  for e in end:
    if DP[e] == INF:
      continue
    DFS(e,e)

T = int(input())
for test in range(T):
  N,M,T = map(int,input().split())
  
  start,g,h = map(int,input().split())
  
  graph = [[] for i in range(N+1)]
  for _ in range(M):
    x,y,w = map(int,input().split())
    graph[x].append((y,w))
    graph[y].append((x,w))
  
  end = []
  for _ in range(T):
    end.append(int(input()))
  path = {}
  result = set()
  Djikstra()
  print(*sorted(result))

간단한 다 익스트라 응용 문제.

 

1.다 익스트라로 최단거리를 찾는다.

2. 이때 최단거리의 경로를 저장해야 하며, 거리가 같은 모든 경로를 다 저장해야 한다.

3. DFS로 경로를 역추적하여 경로상에 g-h 간선이 존재하는지 확인한다.

4. g-h 간선이 존재하는 e를 출력한다.

 

 

오늘의 교훈) 파이썬에서 DFS 사용시 재귀제한을 주의하자