[백준/코틀린] 1504번: 특이한 최단 경로

링크

1504번: 특이한 최단 경로

다익스트라 (Dijkstra)

출처: Wikipedia: Dijkstra’s algorithm

다익스트라란?
그래프의 특정 시작점으로부터 모든 정점까지의 최단 거리를 구하는 알고리즘입니다.

다익스트라 알고리즘의 자세한 설명은 아래 게시글을 확인해주세요.
[백준/코틀린] 1916번: 최소비용 구하기

풀이

다익스트라 알고리즘을 통해 1, v1, v2에서 모든 정점까지의 최단 거리를 미리 구합니다.

v1, v2를 반드시 거쳐 1번에서 N번으로 이동하는 경로는 다음 두 가지뿐입니다.

• 1 → v1 → v2 → N
• 1 → v2 → v1 → N

두 경로의 비용 중 더 작은 값이 최단거리가 됩니다.
경로가 존재하지 않으면(경로 중 이동할 수 없는 구간이 포함된다면) -1을 출력합니다.

코드

import java.util.*

const val INF = Int.MAX_VALUE / 3
lateinit var graph: List<MutableList<Pair<Int, Int>>>
lateinit var distance: List<MutableList<Int>>

fun dijkstra(start: Int) {
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })

    pq.add(start to 0)
    while (pq.isNotEmpty()) {
        val (cur, cd) = pq.poll()

        if (distance[start][cur] > cd) {
            distance[start][cur] = cd
            graph[cur].forEach { (next, w) ->
                pq.add(next to cd + w)
            }
        }
    }
}

fun main() {
    val (n, e) = readln().split(" ").map { it.toInt() }
    graph = List(n + 1) { mutableListOf() }
    distance = List(n + 1) { MutableList(n + 1) { INF } }

    repeat(e) {
        val (a, b, c) = readln().split(" ").map { it.toInt() }

        graph[a] += b to c
        graph[b] += a to c
    }

    val (v1, v2) = readln().split(" ").map { it.toInt() }

    setOf(1, v1, v2).forEach { dijkstra(it) }

    val d1 = distance[1][v1] + distance[v1][v2] + distance[v2][n]
    val d2 = distance[1][v2] + distance[v2][v1] + distance[v1][n]

    println(minOf(d1, d2).takeIf { it < INF } ?: -1)
}