안녕하세요,
재재입니다.
BOJ 1504 특정한 최단 경로 문제 풀이입니다.
BOJ 1504 특정한 최단 경로
(1) 문제 설명
분류 : graph, dijkstra
출처 : https://www.acmicpc.net/problem/1504
(800이하 ) N개의 정점과, (200,000이하) E개의 양방향 간선이 주어집니다.
1번 도시에서 출발해서 n번 도시까지 도착해야하는데,
$$ v_1, v_2 $$ 를 반드시 지나야 하며 이때 최단 거리를 구해주면 됩니다ㅏ.
(2) 풀이 도출
dijkstra 의 시작점을 각각 $$ 1, v_1, v_2 $$ 3개로 해서 3번을 돌리면 됩니다.
그리고 2가지 경우의 수만 가능합니다.
- $$ 1, v_1, v_2, n $$
- $$ 1, v_2, v_1, n $$
즉 1에서 시작해서 $$ v_1, v_2 $$ 중 하나를 방문하고 남은 하나를 방문한 다음,
n 번 노드로 가는 코스트를 사용하면 됩니다.
이때, 시간복잡도는 $$ O(NlogM) $$ 입니다.
(3) 정답 코드
BOJ 1504 특정한 최단 경로