반응형
https://www.acmicpc.net/problem/9370
한 노드에 대한 최단 경로에 특정 경로가 포함되어 있는지를 확인하는 문제이다.
아이디어는 어렵지 않은데, 구현이 복잡하다.
나는 처음에 다익스트라를 한번 돌리면서, 그 과정에 <g, h> 간선이 포함되는지를 체크하려고 하였다.
그런데 최단경로가 여러개인 경우, <g, h> 간선이 포함된 최단 경로를 먼저 고르는 것을 구현하기가 어려워서 이 방법은 포기했다. (나중에 난이도 기여 내역을 보니 이렇게 푼 사람도 있었다.)
그 다음 떠올린 간단한 방법은 다익스트라를 3번 돌리는 것이다.
s 부터 출발하는 다익스트라, g 부터 출발하는 다익스트라, h 부터 출발하는 다익스트라
이렇게 3개를 돌린 결과를 모두 저장한 뒤, 체크할 노드가 check 라고 하면
s -> check == s -> g + g -> h + h -> check
s -> check == s -> h + h -> g + g -> check
이렇게 2가지를 체크해서 둘 중 하나라도 해당되면 답으로 체크해주면 된다.
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
INF = 9876543210
T = int(input())
for _ in range(T):
n, m, t = map(int, input().split())
s, g, h = map(int, input().split())
graph = [[] for _ in range(n+1)]
check_dist = 0
dist_for_h = [INF for _ in range(n + 1)]
for _ in range(m):
a, b, d = map(int, input().split())
graph[a].append((b, d))
graph[b].append((a, d))
if (a == g and b == h) or (a == h and b == g):
check_dist = d
# get dist for s
pq = []
dist_for_s = [INF for _ in range(n + 1)]
dist_for_s[s] = 0
heappush(pq, (0, s))
visit = [False for _ in range(n + 1)]
while pq:
d, node = heappop(pq)
if visit[node]:
continue
for next_node, next_dist in graph[node]:
if not visit[next_node]:
if dist_for_s[next_node] >= dist_for_s[node] + next_dist:
dist_for_s[next_node] = dist_for_s[node] + next_dist
heappush(pq, (dist_for_s[next_node], next_node))
visit[node] = True
# get dist for g
pq = []
visit = [False for _ in range(n+1)]
dist_for_g = [INF for _ in range(n + 1)]
dist_for_g[g] = 0
heappush(pq, (0, g))
while pq:
d, node = heappop(pq)
if visit[node]:
continue
for next_node, next_dist in graph[node]:
if not visit[next_node]:
if dist_for_g[next_node] >= dist_for_g[node] + next_dist:
dist_for_g[next_node] = dist_for_g[node] + next_dist
heappush(pq, (dist_for_g[next_node], next_node))
visit[node] = True
# get dist for h
pq = []
visit = [False for _ in range(n + 1)]
dist_for_h = [INF for _ in range(n + 1)]
dist_for_h[h] = 0
heappush(pq, (0, h))
while pq:
d, node = heappop(pq)
if visit[node]:
continue
for next_node, next_dist in graph[node]:
if not visit[next_node]:
if dist_for_h[next_node] >= dist_for_h[node] + next_dist:
dist_for_h[next_node] = dist_for_h[node] + next_dist
heappush(pq, (dist_for_h[next_node], next_node))
visit[node] = True
check = []
for _ in range(t):
check.append(int(input()))
check.sort()
ans = []
for node in check:
if dist_for_s[node] == dist_for_s[g] + check_dist + dist_for_h[node]:
ans.append(node)
elif dist_for_s[node] == dist_for_s[h] + check_dist + dist_for_g[node]:
ans.append(node)
print(*ans)
똑같은 다익스트라를 3번 적어서 코드는 길지만 내용은 어렵지 않다.
반응형
'알고리즘 (PS) > BOJ' 카테고리의 다른 글
[백준] 30105 - 아즈버의 이빨 자국 (G5) (0) | 2023.10.31 |
---|---|
[백준] 2629 - 양팔저울 (G3) (0) | 2023.10.28 |
[백준] 28458 - Mahjong Tenpai (P5) (0) | 2023.08.27 |
[백준] 28457 - Every? Only One's Marble (G1) (0) | 2023.08.27 |
[백준] 3015 - 오아시스 재결합 (P5) (0) | 2023.07.04 |