結果

問題 No.807 umg tours
ユーザー yudedakoyudedako
提出日時 2020-08-27 13:54:31
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,952 ms / 4,000 ms
コード長 1,252 bytes
コンパイル時間 13,396 ms
コンパイル使用メモリ 456,588 KB
実行使用メモリ 132,224 KB
最終ジャッジ日時 2024-05-03 00:29:44
合計ジャッジ時間 41,600 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 304 ms
57,200 KB
testcase_01 AC 318 ms
57,200 KB
testcase_02 AC 361 ms
57,232 KB
testcase_03 AC 338 ms
57,316 KB
testcase_04 AC 319 ms
57,168 KB
testcase_05 AC 326 ms
57,436 KB
testcase_06 AC 332 ms
57,516 KB
testcase_07 AC 332 ms
57,364 KB
testcase_08 AC 288 ms
57,288 KB
testcase_09 AC 294 ms
57,164 KB
testcase_10 AC 305 ms
57,372 KB
testcase_11 AC 1,434 ms
114,148 KB
testcase_12 AC 1,334 ms
103,432 KB
testcase_13 AC 1,484 ms
109,452 KB
testcase_14 AC 1,150 ms
107,856 KB
testcase_15 AC 1,235 ms
111,868 KB
testcase_16 AC 1,446 ms
107,388 KB
testcase_17 AC 1,912 ms
128,100 KB
testcase_18 AC 1,952 ms
128,136 KB
testcase_19 AC 1,519 ms
117,652 KB
testcase_20 AC 1,385 ms
108,388 KB
testcase_21 AC 1,416 ms
109,416 KB
testcase_22 AC 1,171 ms
108,204 KB
testcase_23 AC 1,076 ms
106,476 KB
testcase_24 AC 1,588 ms
124,040 KB
testcase_25 AC 1,930 ms
132,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*
import kotlin.collections.ArrayList


data class Road(val to: Int, val length: Int)
fun main() {
    val (n, m) = readLine()!!.trim().split(' ').map(String::toInt)
    val nodes = Array(n){ArrayList<Road>()}
    repeat(m) {
        val (a, b, c) = readLine()!!.trim().split(' ').map(String::toInt)
        nodes[a - 1].add(Road(to = b - 1, length = c))
        nodes[b - 1].add(Road(to = a - 1, length = c))
    }
    val memo = Array(2){ LongArray(n){Long.MAX_VALUE} }
    val priorityQueue = PriorityQueue<Triple<Long, Int, Int>>(compareBy(Triple<Long, *, *>::first))
    memo[0][0] = 0
    memo[1][0] = 0
    priorityQueue.add(Triple(0L, 0, 0))
    while (priorityQueue.isNotEmpty()) {
        val (len, use, pos) = priorityQueue.poll()
        if (memo[use][pos] < len) continue
        for ((next, d) in nodes[pos]) {
            if (memo[use][next] > len + d) {
                memo[use][next] = len + d
                priorityQueue.add(Triple(len + d, use, next))
            }
            if (use == 0 && memo[1][next] > len) {
                memo[1][next] = len
                priorityQueue.add(Triple(len, 1, next))
            }
        }
    }
    for (i in 0 until n){
        println(memo[0][i] + memo[1][i])
    }
}
0