1238 파티 (다익스트라)

문제 링크

• 첫 풀이

다익스트라 알고리즘($(V+E)logV$)을 이용하여 각 마을마다 전부(n) 최단 거리를 계산하여 행렬에 저장하여 마을과 x마을과의 거리를 계산하였다.

package `1238`

import java.util.*
import kotlin.collections.ArrayList

fun main() {
    var token = StringTokenizer(readLine()!!)
    val n = token.nextToken().toInt()
    val m = token.nextToken().toInt()
    val x = token.nextToken().toInt() - 1

    val path = Array(n) { ArrayList<Pair<Int, Int>>() }
    val costs = Array(n) { Array(n) { Int.MAX_VALUE } }

    for (_m in 0 until m) {
        token = StringTokenizer(readLine()!!)
        val st = token.nextToken().toInt() - 1
        val ed = token.nextToken().toInt() - 1
        val cost = token.nextToken().toInt()

        path[st].add(Pair(ed, cost))
    }

    for (i in costs.indices) {
        getCosts(i, costs[i], path)
    }

    var ret = -1
    for (r in 0 until n) {
        for (c in 0 until n) {
            if(ret < costs[r][x] + costs[x][r]) {
                ret = costs[r][x] + costs[x][r]
            }
        }
    }

    println("$ret")
}

fun getCosts(x: Int, costs: Array<Int>, path: Array<ArrayList<Pair<Int, Int>>>) {
    val q = PriorityQueue<Pair<Int, Int>>(compareBy({ it.second }, { it.first }))
    q.add(Pair(x, 0))
    costs[x] = 0

    while (!q.isEmpty()) {
        val t = q.poll()
        val st = t.first
        val cost = t.second

        if (costs[st] != cost)
            continue

        for (p in path[st]) {
            val ed = p.first
            val nextCost = p.second
            if (costs[ed] < cost + nextCost)
                continue
            costs[ed] = cost + nextCost
            q.add(Pair(ed, costs[ed]))
        }
    }
}

• 두 번째 풀이

출발접과 도착점의 위치를 뒤집은 인접행렬에서 X마을에서 출발하는 최단 경로를 찾으면 된다. 2번만 탐색하면되므로 시간이 매우 단축된다.

package `1238`

import java.util.*
import kotlin.collections.ArrayList

fun main() {
    var token = StringTokenizer(readLine()!!)
    val n = token.nextToken().toInt()
    val m = token.nextToken().toInt()
    val x = token.nextToken().toInt() - 1

    val path1 = Array(n) { ArrayList<Pair<Int, Int>>() }
    val path2 = Array(n) { ArrayList<Pair<Int, Int>>() }
    val costs = Array(2) { Array(n) { Int.MAX_VALUE } }

    for (_m in 0 until m) {
        token = StringTokenizer(readLine()!!)
        val st = token.nextToken().toInt() - 1
        val ed = token.nextToken().toInt() - 1
        val cost = token.nextToken().toInt()

        path1[st].add(Pair(ed, cost))
        path2[ed].add(Pair(st, cost))
    }

    getCosts(x, costs[0], path1)
    getCosts(x, costs[1], path2)

    var ret = -1
    for (i in 0 until n) {
        if (ret < costs[0][i] + costs[1][i]) {
            ret = costs[0][i] + costs[1][i]
        }
    }

    println("$ret")
}