백준 [1800] kotlin

[문제]

https://www.acmicpc.net/problem/1800

1800번: 인터넷 설치

[풀이]

해결방법을 찾지 못해, 참고한 문제이다..

이분탐색 + 다익스트라 방식으로 해결하는 문제이다.

 

문제에서  제일 가격이 비싼 것에 대해서만 가격을 받기로 하였다. 라는 조건이 있다.

가격으로 들어올 수 있는 최고 금액은 1000000이다.

이분탐색과 다익스트라를 이용하여, 1~1000000까지 중에 최단거리이면서도, 가장 적은 가격을 지불하는 방법을 찾는다.

 

[다익스트라 과정]

다익스트라는 기존의 가중치를 저장하는 배열을 사용했다면, 이번에는 변형하여 할인받을 수 있는 티켓의 수를 저장한다.

 

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.PriorityQueue


lateinit var arr : Array<ArrayList<Edge>>
lateinit var dist : IntArray
var end = 0
var ans = -1
var sale = 0
data class Edge(val node : Int, val weight : Int) : Comparable<Edge>
{
    override fun compareTo(other: Edge): Int {
        return weight - other.weight
    }
}
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    val tmp = br.readLine().split(" ").map{it.toInt()}

    arr = Array(tmp[0]+1){ arrayListOf() }
    end = tmp[0]
    sale = tmp[2]
    repeat(tmp[1])
    {
        val tmp2 = br.readLine().split(" ").map { it.toInt() }
        arr[tmp2[0]].add(Edge(tmp2[1],tmp2[2]))
        arr[tmp2[1]].add(Edge(tmp2[0],tmp2[2]))
    }

    var l = 0
    var r = 1000000

    while (l <= r)
    {
        dist = IntArray(tmp[0]+1){Int.MAX_VALUE}
        val mid = (l + r) / 2
        if(dijkstra(mid)) {
            ans = mid
            r = mid - 1
        } else
        {
          l = mid + 1
        }
    }
    bw.write(ans.toString())
    bw.flush()
    bw.close()
}

fun dijkstra(w : Int) : Boolean
{
    dist[1] = 0
    var pq = PriorityQueue<Edge>()
    pq.add(Edge(1,0))
    while (pq.isNotEmpty())
    {
        val cur = pq.poll()
        arr[cur.node].forEach{
            it ->
            var x = 1
            if(it.weight <= w) x = 0
            if(dist[it.node] > cur.weight + x) {
                dist[it.node] = cur.weight + x
                pq.add(Edge(it.node,cur.weight + x))
            }
        }
    }
    return dist[end] <= sale
}