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 사용시 재귀제한을 주의하자