SaveText.Ru

Без имени
  1. package cities
  2.  
  3. import java.awt.Point
  4. import kotlin.math.ceil
  5.  
  6. data class City(
  7.         val name: String,
  8.         val position: Point
  9. )
  10.  
  11. fun main() {
  12.     val (graph, startEnd) = readInput()
  13.     val (start, end) = startEnd
  14.     val visited = mutableMapOf(start to 0.0)
  15.  
  16.     while (true) {
  17.         val c = graph
  18.                 .filter { it.key.name !in visited && it.value.any { neighbour -> neighbour in visited } }
  19.                 .minBy {
  20.                     it.value
  21.                             .filter { neighbour -> neighbour in visited }
  22.                             .minBy { neighbour -> visited[neighbour] ?: 0.0 }
  23.                             .let { neighbour ->
  24.                                 visited[neighbour]!! + it.key.position.distance(graph[neighbour!!].key.position)
  25.                             }
  26.                 }
  27.  
  28.         if (c == null) {
  29.             println("Path:")
  30.             println("No way")
  31.             return
  32.         }
  33.  
  34.         visited[c.key.name] = c.value
  35.                 .filter { neighbour -> neighbour in visited }
  36.                 .minBy { neighbour -> visited[neighbour] ?: 0.0 }
  37.                 .let { neighbour ->
  38.                     visited[neighbour]!! + c.key.position.distance(graph[neighbour!!].key.position)
  39.                 }
  40.  
  41.         if (c.key.name == end) break
  42.         else {
  43.             visited.filter { it.key in c.value }
  44.                     .forEach { name, distToStart ->
  45.                         if (distToStart > visited[c.key.name]!! + c.key.position.distance(graph[name].key.position))
  46.                             visited[name] = visited[c.key.name]!! + c.key.position.distance(graph[name].key.position)
  47.                     }
  48.         }
  49.     }
  50.  
  51.     println("Path is not greater than ${ceil(visited[end]!!).toInt()}")
  52.     println("Path:")
  53.     println(createPath(graph, visited, start, end).reversed().joinToString(" "))
  54. }
  55.  
  56. fun createPath(graph: Map<City, List<String>>, visited: MutableMap<String, Double>, start: String, end: String) = buildList<String> {
  57.     var a = end
  58.  
  59.     while (a != start) {
  60.         add(a)
  61.  
  62.         a = visited.filter { it.key in graph[a].value }.minBy { it.value }!!.key
  63.     }
  64.     add(start)
  65. }
  66.  
  67. fun readInput(): Pair<Map<City, List<String>>, Pair<String, String>> = readGraph(readSingleInt()) to readStartEnd()
  68.  
  69. fun readGraph(citiesCount: Int): Map<City, List<String>> = buildMap {
  70.     for (i in 0 until citiesCount)
  71.         readCity().run { put(first, second) }
  72. }
  73.  
  74. fun readCity() = readLine()!!.split(" ").let {
  75.     City(it.first(), Point(it[1].toInt(), it[2].toInt())) to it.slice(3..it.lastIndex)
  76. }
  77.  
  78. fun readStartEnd() = readLine()!!.split(" ").toPair()
  79.  
  80. fun readSingleInt(): Int = readLine()?.toInt() ?: 0
  81.  
  82. fun <T> List<T>.toPair() = get(0) to get(1)
  83.  
  84. operator fun Map<City, List<String>>.get(name: String) = asIterable().first { it.key.name == name }
  85.  
  86. inline fun <K, V> buildMap(builderAction: MutableMap<K, V>.() -> Unit): Map<K, V>
  87.         = LinkedHashMap<K, V>().apply(builderAction)
  88.  
  89. inline fun <E> buildList(builderAction: MutableList<E>.() -> Unit): List<E> = ArrayList<E>().apply(builderAction)
  90.  

Share with your friends:

Print