mikhail_dvorkin

Dijkstra Algorithm

Oct 25th, 2021
830
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. fun main() {
  2.     val (n, sIn, fIn) = readInts()
  3.     val s = sIn - 1; val f = fIn - 1
  4.     val inf = Int.MAX_VALUE / 2
  5.     val matrix = List(n) { readInts().map { if (it == -1) inf else it } }
  6.     val mark = BooleanArray(n) // IntArray заполн. 0, BooleanArray — false
  7.     val dist = IntArray(n) { inf }.also { it[s] = 0 }
  8.     while (true) {
  9.         val v = matrix.indices.filter { !mark[it] }.minByOrNull { dist[it] }
  10.             ?.takeIf { dist[it] < inf } ?: break
  11.         mark[v] = true
  12.         for (u in matrix.indices) {
  13.             if (dist[u] > dist[v] + matrix[v][u]) {
  14.                 dist[u] = dist[v] + matrix[v][u]
  15.             }
  16.         }
  17.     }
  18.     println(if (dist[f] < inf) dist[f] else -1)
  19. }
  20.  
  21. fun readLn(): String {
  22.     while (true) {
  23.         val s = readLine()!!.trim()
  24.         if (s.isNotEmpty()) return s
  25.     }
  26. }
  27. fun readStrings() = readLn().split(" ")
  28. fun readInts() = readStrings().map { it.toInt() }
  29.  
RAW Paste Data