[백준/코틀린] 1753번: 최단경로

링크

1753번: 최단경로

풀이

출처: Wikipedia: Dijkstra’s algorithm

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

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

코드

import java.util.*

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

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[cur] > cd) {
            distance[cur] = cd
            graph[cur].forEach { (next, w) ->
                pq.add(next to cd + w)
            }
        }
    }
}

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

    repeat(e) {
        val (u, v, w) = readln().split(" ").map { it.toInt() }

        graph[u] += v to w
    }

    dijkstra(k)
    distance.drop(1).forEach { appendLine(it.takeIf { it != INF } ?: "INF") }

    println(toString())
}