結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2020-08-27 13:54:31 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 2,113 ms / 4,000 ms |
コード長 | 1,252 bytes |
コンパイル時間 | 18,526 ms |
コンパイル使用メモリ | 460,108 KB |
実行使用メモリ | 130,700 KB |
最終ジャッジ日時 | 2024-11-23 20:14:49 |
合計ジャッジ時間 | 45,043 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
import java.util.*import kotlin.collections.ArrayListdata 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] = 0memo[1][0] = 0priorityQueue.add(Triple(0L, 0, 0))while (priorityQueue.isNotEmpty()) {val (len, use, pos) = priorityQueue.poll()if (memo[use][pos] < len) continuefor ((next, d) in nodes[pos]) {if (memo[use][next] > len + d) {memo[use][next] = len + dpriorityQueue.add(Triple(len + d, use, next))}if (use == 0 && memo[1][next] > len) {memo[1][next] = lenpriorityQueue.add(Triple(len, 1, next))}}}for (i in 0 until n){println(memo[0][i] + memo[1][i])}}