백준 9370. 미확인 도착지

tose33 2022. 9. 24. 13:30

9370번: 미확인 도착지

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서

www.acmicpc.net

이 문제에서 요구하는건 위와 같은 그래프가 있을때 시작지점 2에서 도착 후보 지점 6까지의 최단거리가, 1과 3 사이의 간선을 지나는지를 묻는다.

즉 다익스트라를 총 3번 돌리면 된다.

시작지점에서 다른 모든 정점까지의 최단거리.

듀오가 지나간 교차로 g에서 부터 다른 모든 정점까지의 최단 거리.

듀오가 지나간 교차로 h에서 부터 다른 모든 정점까지의 최단 거리.

g,h는 무조건 지나가야 하기 때문에 듀오가 이동할수 있는 방법은 다음 두 가지다.

S -> G -> H -> 도착지점

S -> H -> G -> 도착지점

문제에서 듀오는 항상 최단거리로 이동한다고 했기 때문에 위 두가지 경우 중 작은 값의 경로로 이동한다.

그 값과 시작지점 -> 도착지점의 최단거리가 동일하다면 해당 도착지점 후보는 가능한 도착지점이다.