[BOJ] 10217 KCM Travel - P4

TaeGN·2024년 8월 29일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

40/114

문제풀이

1번 지점에서 1~N까지의 M의 비용으로 가는 최단 시간을 기록하는 dp테이블을 만든다. dp[N][M]
다익스트라를 구현하여 각 지점에서의 비용과 최단 시간을 갱신한다.

주의사항

간선의 입력 데이터를 정렬해주지 않으면 시간 초과를 맞이할 수 있다.

소요시간

2시간

package 백준.Platinum.P4.p10217_KCMTravel

import java.util.PriorityQueue

const val IMPOSSIBLE = Int.MAX_VALUE shr 2
fun main() {
    repeat(readln().toInt()) {
        val (N, M, K) = readln().trim().split(" ").map(String::toInt)
        val roadLists = List(N + 1) { mutableListOf<Triple<Int, Int, Int>>() }
        repeat(K) {
            val (u, v, c, d) = readln().trim().split(" ").map(String::toInt)
            roadLists[u].add(Triple(v, c, d))
        }
        roadLists.forEach { list -> list.sortWith(compareBy({ it.third }, { it.second })) }
        val dp = Array(N + 1) { IntArray(M + 1) { IMPOSSIBLE } }.apply { this[1][0] = 0 }
        val pq = PriorityQueue<Triple<Int, Int, Int>>(compareBy { it.third })
        pq.add(Triple(1, 0, 0))
        while (pq.isNotEmpty()) {
            val (from, totalPrice, totalTime) = pq.poll()
            if (dp[from][totalPrice] < totalTime) continue
            for ((to, price, time) in roadLists[from]) {
                val newTotalPrice = totalPrice + price
                if (newTotalPrice > M) continue
                val newTotalTime = totalTime + time
                if (dp[to][newTotalPrice] > newTotalTime) {
                    for (nextPrice in newTotalPrice..M) {
                        if (dp[to][nextPrice] <= newTotalTime) break
                        dp[to][nextPrice] = newTotalTime
                    }
                    pq.add(Triple(to, newTotalPrice, newTotalTime))
                }
            }
        }

        println(dp[N].min().let { if (it == IMPOSSIBLE) "Poor KCM" else it })
    }
}