안녕하세요,
재재입니다.

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. $$ 1, v_1, v_2, n $$
  2. $$ 1, v_2, v_1, n $$

즉 1에서 시작해서 $$ v_1, v_2 $$ 중 하나를 방문하고 남은 하나를 방문한 다음,
n 번 노드로 가는 코스트를 사용하면 됩니다.

이때, 시간복잡도는 $$ O(NlogM) $$ 입니다.

(3) 정답 코드

BOJ 1504 특정한 최단 경로
태그:                     

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다