結果

問題 No.1065 電柱 / Pole (Easy)
ユーザー 箱星箱星
提出日時 2020-05-29 21:48:11
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 1,298 ms / 2,000 ms
コード長 2,514 bytes
コンパイル時間 16,463 ms
コンパイル使用メモリ 454,024 KB
実行使用メモリ 135,428 KB
最終ジャッジ日時 2024-11-06 03:40:20
合計ジャッジ時間 58,279 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:62:10: warning: parameter 'args' is never used
fun main(args: Array<String>) {
         ^

ソースコード

diff # 

import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

// region
class Edge(val node:Int, val cost:Double)
class State(val cost:Double, val position:Int, val prenode:Int) : Comparable<State> {
    override fun compareTo(other: State): Int {
        return if (cost == other.cost) position.compareTo(other.position) else cost.compareTo(other.cost)
    }
}

fun dijkstra(adj: Array<MutableList<Edge>>, start: Int): Array<Double> {
    val n = adj.count()
    val dist = Array(n) { Double.MAX_VALUE }
    val preNodes = (0 until n).toMutableList()
    val heap = PriorityQueue<State>()
    dist[start] = 0.0
    heap.add(State(0.0, start, 0))
    while (heap.count() > 0) {
        val state = heap.poll()
        val cost = state.cost
        val position = state.position
        val prenode = state.prenode
        if (cost > dist[position]) continue
        preNodes[position] = prenode
        for (edge in adj[position]) {
            val next = State(cost + edge.cost, edge.node, position)
            if (next.cost < dist[next.position]) {
                heap.add(next)
                dist[next.position] = next.cost
            }
        }
    }
    return dist
}
// endregion

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    val m = sc.nextInt()
    val x = sc.nextInt() - 1
    val y = sc.nextInt() - 1
    val pos = Array(n) { sc.nextInt() to sc.nextInt() }
    val adj = Array(n) { mutableListOf<Edge>() }
    for (i in 0 until m) {
        val p = sc.nextInt() - 1
        val q = sc.nextInt() - 1
        val dx = pos[p].first - pos[q].first
        val dy = pos[p].second - pos[q].second
        val d = Math.sqrt((dx * dx + dy * dy).toDouble())
        adj[p].add(Edge(q, d))
        adj[q].add(Edge(p, d))
    }
    val dist = dijkstra(adj, x)
    println(dist[y])
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}
0