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

문제

입력

• 첫 번째 줄에는 테스트 케이스의 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개로 향하는 최단 경로의 일부이다.

출력

• 테스트 케이스마다

입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

풀이

# 백준 9370 미확인 도착지
import heapq
import sys
input = sys.stdin.readline
INF =int(1e9)

def dijkstra(start, distance):
    distance[start] =0
    q =[]
    heapq.heappush(q,(0,start))
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in array[now]:
            cost = dist + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost                
                heapq.heappush(q,(cost,i[0]))



T = int(input())
result = [[] for _ in range(T)]
for c in range(T):
    n,m,t = map(int,input().split())
    s,g,h = map(int,input().split())
    array = [[] for _ in range(n+1)]
    distance =[INF for _ in range(n+1)]
    dist_g = [INF for _ in range(n+1)]
    dist_h = [INF for _ in range(n+1)]
    ends= []
    for _ in range(m):
        a,b,d = map(int,input().split())
        array[a].append([b,d])
        array[b].append([a,d])
    for _ in range(t):
        heapq.heappush(ends,int(input()))
    dijkstra(s, distance)
    dijkstra(g, dist_g)
    dijkstra(h, dist_h)
    for end in ends:
        if (distance[end] == distance[g] + dist_g[h] + dist_h[end]) or (distance[end] == distance[h] + dist_h[g] + dist_g[end]):
            heapq.heappush(result[c], end)
        
for i in result:
    i.sort()
    print(*i)

후기

• 해당 문제를 푸는 데에 있어서 가장 어려웠던 점은 아이디어를 떠올리는 점하고 시간 복잡도를 고려하고 푸는 것과 그리고 정렬하여 어떻게 출력하는 데에 있어서 시간이 오래 걸렸다. 으어 언제쯤에 적응할 수 있을까. 걱정이 된다.