백준 17835번 면접보는 승범이네 Kotlin

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

문제

---

생각하기

---

• 다익스트라

• 최단거리 그래프 문제

• 방향을 거꾸로 해야하는 문제

동작

결과

코드

---

import java.io.File
import java.util.PriorityQueue
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var M = 0
private var K = 0
private const val INF = Long.MAX_VALUE
private lateinit var adjList: MutableList<MutableList<Edge>>
private lateinit var interviewRooms: MutableList<Int>

private data class Edge(val num: Int, val dist: Long) : Comparable<Edge> {
    override fun compareTo(o: Edge): Int {
        return dist.compareTo(o.dist)
    }
} // End of Edge class

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val ret = dijkstra()
    var max = -1L
    var num = 0
    for (i in 1..N) {
        if (ret[i] != INF) {
            if (max < ret[i]) {
                max = ret[i]
                num = i
            }
        }
    }

    sb.append(num).append('\n').append(max)
    return sb.toString()
} // End of solve()

private fun dijkstra(): LongArray {
    val que = PriorityQueue<Edge>()
    val isVisited = BooleanArray(N + 1)
    val dist = LongArray(N + 1) { INF }

    interviewRooms.forEach { it ->
        que.offer(Edge(it, 0))
        dist[it] = 0
    }


    while (que.isNotEmpty()) {
        val cur = que.poll()

        if (dist[cur.num] < cur.dist) continue
        if (isVisited[cur.num]) continue
        isVisited[cur.num] = true

        for (next in adjList[cur.num]) {

            if (dist[next.num] > dist[cur.num] + next.dist) {
                dist[next.num] = dist[cur.num] + next.dist
                que.offer(Edge(next.num, dist[next.num]))
            }
        }
    }

    return dist
} // End of dijkstra()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        M = nextToken().toInt()
        K = nextToken().toInt()
    }

    adjList = mutableListOf()
    repeat(N + 1) {
        adjList.add(mutableListOf())
    }

    repeat(M) {
        StringTokenizer(br.readLine()).run {
            val u = nextToken().toInt()
            val v = nextToken().toInt()
            val c = nextToken().toLong()
            adjList[v].add(Edge(u, c))
        }
    }

    interviewRooms = mutableListOf()
    StringTokenizer(br.readLine()).run {
        repeat(K) {
            interviewRooms.add(nextToken().toInt())
        }
    }
} // End of input()