結果

問題 No.1065 電柱 / Pole (Easy)
ユーザー 👑 箱箱
提出日時 2020-05-29 21:48:11
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,239 ms / 2,000 ms
コード長 2,514 bytes
コンパイル時間 14,024 ms
コンパイル使用メモリ 445,616 KB
実行使用メモリ 134,656 KB
最終ジャッジ日時 2024-04-23 21:20:52
合計ジャッジ時間 52,812 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 293 ms
51,272 KB
testcase_01 AC 291 ms
51,268 KB
testcase_02 AC 976 ms
108,740 KB
testcase_03 AC 1,067 ms
120,748 KB
testcase_04 AC 982 ms
120,484 KB
testcase_05 AC 884 ms
118,444 KB
testcase_06 AC 907 ms
118,272 KB
testcase_07 AC 574 ms
93,432 KB
testcase_08 AC 906 ms
134,656 KB
testcase_09 AC 485 ms
67,460 KB
testcase_10 AC 698 ms
106,924 KB
testcase_11 AC 593 ms
93,216 KB
testcase_12 AC 550 ms
90,028 KB
testcase_13 AC 872 ms
105,280 KB
testcase_14 AC 1,050 ms
108,300 KB
testcase_15 AC 1,031 ms
122,444 KB
testcase_16 AC 951 ms
92,588 KB
testcase_17 AC 1,090 ms
121,720 KB
testcase_18 AC 733 ms
91,676 KB
testcase_19 AC 1,239 ms
121,920 KB
testcase_20 AC 743 ms
91,712 KB
testcase_21 AC 789 ms
91,480 KB
testcase_22 AC 1,063 ms
119,092 KB
testcase_23 AC 402 ms
56,008 KB
testcase_24 AC 402 ms
56,208 KB
testcase_25 AC 549 ms
89,560 KB
testcase_26 AC 904 ms
104,036 KB
testcase_27 AC 895 ms
102,500 KB
testcase_28 AC 1,082 ms
117,100 KB
testcase_29 AC 534 ms
69,796 KB
testcase_30 AC 1,179 ms
123,496 KB
testcase_31 AC 951 ms
107,892 KB
testcase_32 AC 812 ms
93,344 KB
testcase_33 AC 1,036 ms
124,004 KB
testcase_34 AC 808 ms
92,228 KB
testcase_35 AC 1,095 ms
122,540 KB
testcase_36 AC 331 ms
52,332 KB
testcase_37 AC 413 ms
56,228 KB
testcase_38 AC 335 ms
52,460 KB
testcase_39 AC 409 ms
55,944 KB
testcase_40 AC 306 ms
51,984 KB
testcase_41 AC 1,239 ms
134,416 KB
testcase_42 AC 752 ms
93,560 KB
testcase_43 AC 944 ms
107,784 KB
testcase_44 AC 674 ms
90,412 KB
testcase_45 AC 976 ms
108,516 KB
testcase_46 AC 288 ms
51,484 KB
testcase_47 AC 301 ms
51,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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