[baekjoon] #1238: 파티

Problem Link

• Find all dijkstra results of vertexes.
• If the start node is same as "x", accumulate all distance results of vertexes.
• Otherwise, accumulate distance of "x" only.
• Because we want to get shortest path from x to other vertexes and vice versa.

import java.util.*

private lateinit var graph: Array<MutableList<Pair<Int, Int>>>
private lateinit var result: Array<Int>
private lateinit var distance: Array<Int>
private lateinit var queue: PriorityQueue<Pair<Int, Int>>

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val (n, m, x) = br.readLine().split(" ").map { it.toInt() }
    graph = Array(n + 1) { mutableListOf() }
    result = Array(n + 1) { 0 }
    for (i in 0 until m) {
        val (src, dest, time) = br.readLine().split(" ").map { it.toInt() }
        graph[src].add(Pair(dest, time))
    }

    for (i in 1..n) {
        dijkstra(n, i, x)
    }
    bw.write("${result.maxOf { it }}")

    br.close()
    bw.close()
}

fun dijkstra(n: Int, start: Int, x: Int) {
    distance = Array(n + 1) { Int.MAX_VALUE }
    distance[start] = 0
    queue = PriorityQueue(compareBy { it.second })
    queue.add(Pair(start, 0))

    while (queue.isNotEmpty()) {
        val (curr, currDistance) = queue.poll()
        for ((next, nextDistance) in graph[curr]) {
            if (distance[next] < currDistance) continue
            if (currDistance + nextDistance < distance[next]) {
                distance[next] = currDistance + nextDistance
                queue.add(Pair(next, distance[next]))
            }
        }
    }
    if (start == x) {
        for (i in 1..n) {
            result[i] += distance[i]
        }
    } else {
        result[start] += distance[x]
    }
}

Time Complexity

O(n (n + m) logn)