미확인 도착지

❓문제

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

❗문제 정리

💡 다른 문제와 달리 지나가야하는 특정지점 g, h가 존재
시작지점 ->g->h->도착지점 / 시작지점 ->h->g->도착지점의 거리가 시작지점->도착지점의 거리와 같으면 시작지점에서 도착지점까지 갈 때, g->h 또는 h->g를 지난 것!!
💡양방향 간선이므로 도착지점의 인덱스에 (시작지점, 둘사이 거리) 넣어주기

• 다익스트라 알고리즘
• 양방향 간선 사용 -> 도착지점 인덱스에도 (시작지점, 거리) 넣어주기

📑코드

import heapq

def heap_dijkstra(n,start,graph):
    q=[]
    INF=int(1e9)
    distance=[INF]*(n+1)
  #1. 시작노드의 distance값을 0으로 초기화
    heapq.heappush(q,(0,start))
    distance[start]=0
  #큐에서 최단거리가 가장 짧은거 꺼내고
    while q:
        dist, now=heapq.heappop(q)#(거리, 현재 노드번호)
  #현재 노드가 이미 처리되었으면 무시==꺼낸 길이 dist가 더 길면 무시
        if dist>distance[now]:
            continue
  #아닌 경우, 현재 노드와 연결된 노드 확인하고 기존길이+뉴길이
        for i in graph[now]:#현재 노드 번호에는 (노드,거리)
            cost=dist+i[1]
            if cost<distance[i[0]]:
                distance[i[0]]=cost
                heapq.heappush(q, (cost, i[0]))
    return distance

#입력------------------------------------------------------
T=int(input())
for i in range(T):
    n, m,t=map(int, input().split())# #교차로, #도로 #목적지후보
    s,g,h=map(int, input().split())#start, 교차로 사이의 도로를 건너야함
    
    graph=[[]for _ in range(n+1)]
    for i in range(m):
        a,b,d=map(int, input().split())
        graph[a].append((b,d))
        graph[b].append((a,d))

    t_=[]
    for i in range(t):
        t_.append(int(input()))
#---------------------------------------------------------
#다익스트라 진행
    start_=heap_dijkstra(n, s, graph)#예술가 출발부분부터
    g_=heap_dijkstra(n, g, graph)#꼭 지나가야하는 v1노드부터
    h_=heap_dijkstra(n, h, graph)#꼭 지나가야하는 v2노드부터
#---------------------------------------------------------
#예술가 출발부분부터 v1노드까지 +v1노드에서 v2노드 지나고+v2노드에서 후보 도착
#예술가 출발부분부터 v2노드까지 +v2노드에서 v1노드 지나고+v1노드에서 후보 도착
#한게 예술가 출발부터 후보도착지 까지 간것들이랑 같으면 후보 목적지 확정내기
#일반 다익스트라랑 값이 같다==일반 다익스트라 계산할때도 지정 노드 지나감!!
    targets=[]
    for target in t_:
        if start_[g]+g_[h]+h_[target]==start_[target] or start_[h]+h_[g]+g_[target]==start_[target]:
            targets.append(target)
    targets.sort()#문제에서 오름차순하라고함
#------------------------------------------------------------------------------------
#확정낸 후보 목적지 출력
    for destination in targets:
        print(destination, end=' ')

🎖제출 결과

💡insight

특정한 최단 경로 문제와 푸는 방식이 같음
목적지가 2개 이상 있다는 것만 다름.