[白俊]1774号と宇宙神との交感

伯準-1774号と宇宙神の交感
質問する
質問する
黄仙子は宇宙神と交流できる魂です.しかし、宇宙神は一つだけではないので、黄仙子は毎回多くの宇宙神と交流しなければならない.このような状況で、新しい宇宙神は黄仙子を利用した.
しかし、偉大な宇宙神たちは黄仙子と直接結びつく必要はない.黄仙子や宇宙神と交流できる宇宙神がいるので、新しい宇宙神はそれらの宇宙神を通じて黄仙子と交流することができます.
宇宙神との交流は、宇宙神と皇太子や宇宙神の間の精神通路を通じて行われる.しかし、宇宙神との交流は難しいので、黄仙子はこれらの通路が長いのが好きではありません.通路が長ければ長いほど、大変なので.
また、私たちは3次元座標系で表すことができる世界に住んでいますが、宇宙神と黄仙子は2次元座標系で表すことができる世界に住んでいます.チャネルの長さは2 D座標系の距離に等しい.
すでに皇太子氏につながる、あるいは宇宙神につながる通路が存在する.私たちは黄善子さんを助けて、まだつながっていない宇宙神をつなぎます.再創造が必要な精神通路の長さの総和を最小にし、通路を作り出し、「パンベッド」を叫ぶのを助ける.
方法
この問題は,すべての頂点がN−1本の幹線で接続された伸長木で解決され,その中で最小でなければならないのでMSTで解く.
MSTを作成する貪欲な方法としてKruskal,Primアルゴリズムがある.以前はKruskalで問題を解いていたので、Primで挑戦.
Primは頂点からツリーを展開します.次に、MSTは、木に接続された幹線の中で循環構造を形成しない幹線の中で最も長さの小さい幹線を選択することによって実現される.
コード#コード#

import java.lang.Math.hypot
import java.util.*

class IO1774 {
    private val br = System.`in`.bufferedReader()
    private val bw = System.out.bufferedWriter()

    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
    fun getRow() = br.readLine().split(" ").map{ it.toInt() }
}

fun main() {
    val io = IO1774()
    val (N, M) = io.getRow()

    fun getArray(num: Int): Array<List<Int>> {
        return Array(num) {
            io.getRow()
        }
    }

    val positionArr = getArray(N)
    val distanceArr = Array(N) { Array(N) { Double.MAX_VALUE } }

    fun getDistance(p1: List<Int>, p2: List<Int>): Double {
        val (x1, y1) = p1
        val (x2, y2) = p2
        return hypot((x1-x2).toDouble(), (y1-y2).toDouble())
    }

    for (i in 0 until N) {
        val p1 = positionArr[i]
        for (j in i+1 until N) {
            val p2 = positionArr[j]
            val dis = getDistance(p1, p2)
            distanceArr[i][j] = dis
            distanceArr[j][i] = dis
        }
    }

    val visited = Array(N) { false }

    repeat(M) {
        val (p1, p2) = io.getRow()
        distanceArr[p1-1][p2-1] = 0.0
        distanceArr[p2-1][p1-1] = 0.0
    }

    data class Edge(val source: Int, val dest: Int, val cost: Double)
    val pq = PriorityQueue<Edge>(compareBy { it.cost })
    for(row in 1 until N) {
        pq.add(Edge(0, row, distanceArr[0][row]))
    }
    var answer: Double = 0.0
    var edge = 0
    visited[0] = true
    while (edge < N - 1) {
        val e = pq.poll()
        val (sour, dest, cost) = e

        if (visited[dest]) continue
        visited[dest] = true
        answer += cost
        edge++

        if (cost == Double.MAX_VALUE) continue

        for (row in 0 until N) {
            if (dest == row) continue
            pq.add(Edge(dest, row, distanceArr[dest][row]))
        }
    }
    io.write(String.format("%.2f", answer))
    io.close()
}