[Python]최단경로 백준 9370

   문제

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

후보지까지의 최단거리가 g->h로 가는길을 지나고 있는가를 물어보는 문제이다.

s->g->h->c 가 s->c이거나 s->h->g->c가 s->c이면 후보지가 될수있는것이다.

문제를 차분히 읽어보면 그렇게 복잡한 문제는 아니다.

import sys
import heapq
 
def Dijkstra(start,n):#출발점 노드개수
    q=[]
    heapq.heappush(q,[0,start])
    INF=sys.maxsize
    result=[INF for _ in range(n+1)]
    result[start]=0
    while q:
        dis,start=heapq.heappop(q)
        if dis>result[start]:
            continue
        for d,x in G[start]:
            d+=dis
            if d<result[x]:
                result[x]=d
                heapq.heappush(q,[d,x])
 
 
    return result
 
 
 
 
 
T=int(sys.stdin.readline())
for _ in range(T):
    n,m,t=map(int,sys.stdin.readline().split())#교차로,도로,목적지 후보의 개수
    s,g,h=map(int,sys.stdin.readline().split())#예술가들의 출발지,거쳐가는 길에 연결된 노드들
    G=[[] for _ in range(n+1)]
    for _ in range(m):#양방향
        a,b,d=map(int,sys.stdin.readline().split())#노드1,노드2,거리
        G[a].append([d,b])
        G[b].append([d,a])
 
    candidate=[]
 
    for _ in range(t):
        candidate.append(int(sys.stdin.readline()))
 
 
    #출발점에서 거쳐가는길에 연결된 노드
    #거쳐가는길에 연결된 노드에서 후보지로 가는경우 모두확인
    #출발점에서 후보지까지의 거리와 거쳐가는길을 통해 후보지로 간 거리를 비교하여 같은거 출력
    result=[]
    distanses = Dijkstra(s,n)#출발지에서의 거리들
    distanses_node1=Dijkstra(g,n)#g에서 출발
    distanses_node2=Dijkstra(h,n)#h에서 출발
    distanse_g_h=0
    for d,x in G[g]:#g->h까지의 거리
        if x==h:
            distanse_g_h=d
            break
    for c in candidate:#후보지들 하나씩 비교
        #s->g->h->c이 s->c와 같거나
        #s->h->g->c가 s->c와 같다면 후보지이다.
        if distanses[c]==distanses[g]+distanse_g_h+distanses_node2[c] or distanses[c]==distanses[h]+distanse_g_h+distanses_node1[c]:
            result.append(c)
 
    result.sort()
    print(*result)
    # for i in result:
    #     print(i,end=" ")