[백준/BOJ] 13424번: 비밀 모임

문제

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

13424번: 비밀 모임

해설

각 방 사이 비밀 통로를 이용하는 비용이 나와있다.

플로이드 와샬 알고리즘을 이용하여 각 방 사이를 오가는데 필요한 최소 거리를 구해놓은 후,

현재 친구들이 있는 방에서 각 방까지 가장 작은 비용으로 갈 수 있는 방을 찾으면 된다.

코드

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

private lateinit var map: Array<IntArray>
private const val INF = 987654321

fun main() = with(System.`in`.bufferedReader()) {
    val testCase = readLine().toInt()
    repeat(testCase) { i ->
        val (roomCnt, secretPassageCnt) = readLine().split(" ").map { it.toInt() }

        map = Array(roomCnt + 1) { IntArray(roomCnt + 1) }
        for(i in 1 .. roomCnt) {
            for(j in 1 .. roomCnt) {
                if(i == j) map[i][j] = 0
                else map[i][j] = INF
            }
        }

        repeat(secretPassageCnt) {
            val (from, to, cost) = readLine().split(" ").map { it.toInt() }
            map[from][to] = cost
            map[to][from] = cost
        }

        val friendCnt = readLine().toInt()

        val locateFriendRoom = ArrayList<Int>()
        val st = StringTokenizer(readLine())
        repeat(friendCnt) {
            locateFriendRoom.add(st.nextToken().toInt())
        }


        floyd(roomCnt)

        var ans = 0
        var move = Integer.MAX_VALUE
        for(i in 1 .. roomCnt) {
            var temp = 0
            for(j in locateFriendRoom) {
                if(i == j) continue
                temp += map[j][i]
            }

            if(move > temp) {
                move = temp
                ans = i
            }
        }

        println(ans)
    }
}

private fun floyd(n: Int) {
    for(k in 1 .. n) {
        for(i in 1 .. n) {
            for(j in 1 .. n) {
                map[i][j] = min(map[i][j], map[i][k] + map[k][j])
            }
        }
    }
}