[백준/9370/파이썬] 미확인 도착지

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

9370번: 미확인 도착지

Problem

• (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. 
• 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.
• 이 듀오는 대체 어디로 가고 있는 것일까?

조건

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

SOL

G,H를 꼭 지나서 , 최단경로로, 우회하지 않고 우리가 생각하는 후보군에 도달 했을 때, edge들의 가중치가 어떻게 되는지 확인하는 문제이다.

이때, G,H를 지나는 걸 생각해보면,

시작점 -> G -> H -> END

시작점 -> H -> G -> END 

2가지 경우가 있다.

그렇다면, 우리는 시작점 ->G/H까지 가는데,최단경로를 알아야하고, G-H 사이의 거리를 알아야하고, G/H->END까지 최단 경로를 알아야한다.

 

가중치가 있는 그래프를 최단경로로 돌기위해서 가장 대표적인게 다익스트라 알고리즘이다.

#미확인 도착지
# 그래프 문제, 다익스트라 
import sys
import heapq
input= sys.stdin.readline

tc=int(input().rstrip())

def Dijkstra(start,n):
    hq=[]
    heapq.heappush(hq,[0,start])
    INF=sys.maxsize
    result = [INF for _ in range(n+1)]
    result[start]=0
    while hq:
        dist,node=heapq.heappop(hq)
        #이미 방문을 했다면
        if dist>result[node]:
            continue
        for v in graph[node]:
            neighbor=v[0]
            n_cost=result[node] + v[1]
            if n_cost<result[neighbor]:
                result[neighbor] = n_cost
                heapq.heappush(hq,[n_cost,neighbor])
    return result

while tc:
    N,M,T=map(int,input().split())
    start,g,h=map(int,input().split())
    graph=[[] for _ in range(N+1)]
    ans=[]
    for _ in range(M):
        a,b,value=map(int,input().split())
        graph[a].append((b,value))
        graph[b].append((a,value))
    endPoint=[]
    for _ in range(T):
        endPoint.append(int(input().rstrip()))
    dist=Dijkstra(start,N)
    g_dist=Dijkstra(g,N)
    h_dist=Dijkstra(h,N)
    dist_gToh=0
    for x,d in graph[g]:
        if x==h:
            dist_gToh=d
            break
    for e in endPoint:
        if dist[e] == (dist[g]+dist_gToh+h_dist[e]) or dist[e]==(dist[h]+dist_gToh+g_dist[e]):
            ans.append(e)
    ans.sort()
    print(*ans)
    tc-=1