백준 1446번
https://www.acmicpc.net/problem/1446

문제

---

생각하기

---

• 다익스트라 문제이다.

동작

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var D = 0
private const val INF = Int.MAX_VALUE

private lateinit var adjList: MutableList<MutableList<Road>>
private var dist = IntArray(10001) { INF }

private data class Road(var location: Int, var dist: Int) : Comparable<Road> {
    override fun compareTo(other: Road): Int {
        return dist - other.dist
    } // End of compareTo
} // End of Road class

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val sb = StringBuilder()

    input()

    dijkstra()
    sb.append(dist[D])
    
    bw.write(sb.toString())
    bw.close()
} // End of main

private fun dijkstra() {
    val pque = PriorityQueue<Road>()
    pque.offer(Road(0, 0))
    dist[0] = 0

    while (pque.isNotEmpty()) {
        val poll = pque.poll()

        if (poll.dist != dist[poll.location]) continue
        if(poll.location >= D) continue

        val size = adjList[poll.location].size
        for (i in 0 until size) {
            val nextRoad = adjList[poll.location][i]

            if (dist[nextRoad.location] > dist[poll.location] + nextRoad.dist) {
                dist[nextRoad.location] = dist[poll.location] + nextRoad.dist
                pque.offer(Road(nextRoad.location, dist[nextRoad.location]))
            }
        }
    }
} // End of dijkstra

private fun input() {
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt() // 지름길의 개수
    D = st.nextToken().toInt() // 고속도로의 길이

    adjList = ArrayList()
    for(i in 0 until D) {
        adjList.add(ArrayList())
        adjList[i].add(Road(i + 1, 1))
    }

    for (i in 0 until N) {
        st = StringTokenizer(br.readLine())
        val startLocation = st.nextToken().toInt() // u
        val endLocation = st.nextToken().toInt() // v
        val dist = st.nextToken().toInt() // w

        // 역주행 불가
        if (endLocation > D) continue

        // 원래 가는 길이보다 지름길의 길이가 같거나 큰 경우
        if (dist >= (endLocation - startLocation)) continue
        adjList[startLocation].add(Road(endLocation, dist))
    }
} // End of input