/** * So lets try something else. Idea is to dykstra, until all nodes are visited. Should be O (n log n). */ import java.util.PriorityQueue import kotlin.math.pow import kotlin.math.sqrt fun main() { val reader = System.`in`.bufferedReader() val n = reader.readLine().toInt() val input = reader.lineSequence().take(n).map { string -> string.split(" ", limit = 3) .map { it.toDouble() } .let { (x, y, z) -> Coordinate(x, y, z) } }.toList() val seen = mutableSetOf() val start = input.first() val queue = PriorityQueue> { o1, o2 -> o1.second.compareTo(o2.second) } queue.add(start to Double.MAX_VALUE) var shortest = Double.MAX_VALUE while (queue.isNotEmpty()) { val (current, distance) = queue.remove() if (current in seen) continue seen.add(current) shortest = distance.coerceAtMost(shortest) input.filter { it !in seen }.map { it to current.distance(it) }.toCollection(queue) if (seen.size == input.size) break } println(shortest) } typealias Coordinate = Triple inline fun Coordinate.distance(other: Coordinate) = sqrt((first - other.first).pow(2) + (second - other.second).pow(2) + (third - other.third).pow(2))