[BOJ 23801] 백준 23801번 - 두 단계 최단 경로 2

1. 문제

$23801$. 두 단계 최단 경로 2

백준 23801번 - 두 단계 최단 경로 2 (https://www.acmicpc.net/problem/23801)

2. 풀이

어느 한 점에서 다른 한 점으로 가는 최단거리를 구하는 문제이므로, Dijkstra 다익스트라 알고리즘을 사용한다.

출발 정점 $X$에서 다익스트라를 사용하면, $P$개의 중간 정점까지의 최소 거리가 전부 나온다. 다만, $P$개의 중간 정점에서 $Z$까지 각각의 거리를 구한다 생각하면 다익스트라를 $P(1\leq P\leq N-3)$번 하는 것이기 때문에 너무 많은 시간이 소요된다.

단순하게 출발점과 도착점을 바꿔 생각하면 된다. 다익스트라는 출발점이 한 개이고 도착점은 어느 점이든 몇 개든 상관이 없다는 성질을 파악해야 한다. 따라서 각각의 $P$에서 $Z$로 가는 것이 아니라 $Z$에서 다익스트라를 사용하면 된다.

결론적으로 $X$에서 다익스트라를 사용하여 각각의 $P$개의 정점까지의 거리 Dist[0][p]를 구할 수 있고, $Z$에서 다익스트라를 사용하여 각각의 $P$개의 정점까지의 거리 Dist[1][p]를 구할 수 있다. 각각의 $p$점에 대해서 Dist[0][p] + Dist[1][p]의 최솟값을 찾으면 된다.

3. 채점 결과

4. 회고

long long int 자료형을 사용해야 하는데 int를 사용해서 WA를 한 번 받았다.

5. 코드