[백준] 최소비용 구하기 (1916)(Kotlin)

원본 문제 : https://www.acmicpc.net/problem/1916

 

<첫번째> 성공(Adjacency List)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.ArrayList

class Node : Comparable<Node> {
    var index = 0
    var distance = 0

    constructor(index: Int, distance: Int) {
        this.index = index
        this.distance = distance
    }

    override fun compareTo(other: Node): Int {
        return this.distance - other.distance
    }
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    val n = readLine().toInt()
    val m = readLine().toInt()

    val list: ArrayList<PriorityQueue<Node>> = ArrayList<PriorityQueue<Node>>()

    for ( i in 0 until m+2 ) {
        list.add(PriorityQueue<Node>())
    }

    for ( i in 1 until m+1 ) {
        val str = readLine().split(" ")
        val a = str[0].toInt()
        val b = str[1].toInt()
        val c = str[2].toInt()
        list[a].add(Node( b, c ))
    }

    val sd = readLine().split(" ")
    val start = sd[0].toInt()
    val dest = sd[1].toInt()

    var distance: IntArray = IntArray( n+1 )
    Arrays.fill(distance, Int.MAX_VALUE)

    var check: BooleanArray = BooleanArray( n+1 )
    val pq: PriorityQueue<Node> = PriorityQueue<Node>()
    distance[start] = 0
    pq.add(Node(start, 0))

    while ( !pq.isEmpty() ) {

        val now: Int = pq.poll().index

        if ( check[now] ) continue
        check[now] = true

        for ( node in list[now] ) {
            if ( distance[node.index] > distance[now] + node.distance ) {
                distance[node.index] = distance[now] + node.distance
                pq.add(Node(node.index, distance[node.index]))
            }
        }
    }

    println(distance[dest])

}