백준 - 9370번(다익스트라, DP)

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

9370번: 미확인 도착지

 

import sys
from collections import deque

def dajik(st, ed):
    if st == ed:
        return 0

    q = deque([])
    q.append([0, st])
    dist = [float('inf')] * (n + 1)

    while q:
        now_value, st = q.popleft()
        for i in arr[st]:
            if now_value + i[1] < dist[i[0]]:
                dist[i[0]] = now_value + i[1]
                q.append([now_value + i[1], i[0]])

    return dist[ed]

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())
    arr = [[] for _ in range(n+1)]

    for _ in range(m):
        a, b, c = map(int, sys.stdin.readline().split())
        arr[a].append([b, c])
        arr[b].append([a, c])

    end = []
    ans = []

    for _ in range(t):
        end.append(int(sys.stdin.readline()))

    for j in end:
        p1 = dajik(s, g) + dajik(g, h) + dajik(h, j)
        p2 = dajik(s, h) + dajik(h, g) + dajik(g, j)
        r_ans = min(p1,p2)
        r_p = dajik(s, j)

        if r_ans == r_p and r_ans != float('inf'):
            ans.append(j)
    ans.sort()

    print(*ans)

바로 앞 게시글에서 푼 문제와 매우 흡사하다.

특정 조건을 만족하면서 최단거리를 찾는 거다.

문제 조건에 따라서 g, h를 반드시 지나가야 하는데 이때 g, h에 우선순위가 존재하지 않으므로 각각 먼저 갈 경우 두 가지 case를 고려해야 한다. 둘 중 최단 거리 case와 s부터 j까지의 최단 거리가 동일하다면 문제 조건에 맞는 답안이기 때문에 ans에 추가해 준다.

이때 둘 다 값이 float('inf')일 경우 조건문에는 만족하지만 문제에서 제시한 조건에 만족하지 않기 때문에 그럴 경우 걸러줄 필요가 있다.

ans 배열을 오름차순으로 정렬한 후 출력하면 끝!