結果

問題 No.1812 Uribo Road
ユーザー yudedakoyudedako
提出日時 2022-01-25 20:09:36
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,353 ms / 5,000 ms
コード長 3,029 bytes
コンパイル時間 15,973 ms
コンパイル使用メモリ 455,864 KB
実行使用メモリ 93,948 KB
最終ジャッジ日時 2024-05-09 21:18:56
合計ジャッジ時間 40,921 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 323 ms
55,256 KB
testcase_01 AC 321 ms
55,132 KB
testcase_02 AC 327 ms
55,128 KB
testcase_03 AC 445 ms
61,260 KB
testcase_04 AC 317 ms
54,992 KB
testcase_05 AC 319 ms
55,344 KB
testcase_06 AC 328 ms
55,132 KB
testcase_07 AC 418 ms
59,432 KB
testcase_08 AC 557 ms
60,728 KB
testcase_09 AC 498 ms
61,416 KB
testcase_10 AC 473 ms
60,604 KB
testcase_11 AC 428 ms
56,740 KB
testcase_12 AC 1,059 ms
91,916 KB
testcase_13 AC 986 ms
92,388 KB
testcase_14 AC 907 ms
91,868 KB
testcase_15 AC 783 ms
80,024 KB
testcase_16 AC 816 ms
85,412 KB
testcase_17 AC 1,118 ms
92,960 KB
testcase_18 AC 877 ms
73,688 KB
testcase_19 AC 1,146 ms
93,016 KB
testcase_20 AC 1,353 ms
93,344 KB
testcase_21 AC 1,129 ms
93,948 KB
testcase_22 AC 1,139 ms
93,600 KB
testcase_23 AC 487 ms
60,968 KB
testcase_24 AC 337 ms
55,492 KB
testcase_25 AC 663 ms
71,192 KB
testcase_26 AC 398 ms
56,628 KB
testcase_27 AC 842 ms
72,776 KB
testcase_28 AC 719 ms
78,584 KB
testcase_29 AC 323 ms
55,468 KB
testcase_30 AC 563 ms
64,380 KB
testcase_31 AC 1,081 ms
85,564 KB
testcase_32 AC 453 ms
59,992 KB
testcase_33 AC 1,069 ms
91,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*


fun minDistance(start: Int, graph: List<List<Pair<Int, Int>>>): IntArray {
    val minDistance = IntArray(graph.size){Int.MAX_VALUE}.also{it[start] = 0}
    val queue = PriorityQueue<Pair<Int, Int>>(compareBy{it.second}).also { it.add(start to 0) }
    while (queue.isNotEmpty()) {
        val (current, cost) = queue.remove()
        if (minDistance[current] < cost) continue
        for ((next, diff) in graph[current]) {
            if (minDistance[next] > cost + diff) {
                minDistance[next] = cost + diff
                queue.add(next to cost + diff)
            }
        }
    }
    return minDistance
}
fun main() {
    val (n, m, k) = readLine()!!.split(' ').map(String::toInt)
    val pigRoad = readLine()!!.split(' ').map{it.toInt() - 1}
    val edges = List(m){
        val (a, b, c) = readLine()!!.split(' ').map(String::toInt)
        Triple(a - 1, b - 1, c)
    }
    val graph = List(n){ mutableListOf<Pair<Int, Int>>() }
    for ((a, b, c) in edges) {
        graph[a].add(b to c)
        graph[b].add(a to c)
    }
    val pigVertices = pigRoad.map { i ->
        val (a, b, _) = edges[i]
        listOf(a, b)
    }
    val fromStart = minDistance(0, graph)
    val fromGoal = minDistance(n - 1, graph)
    val minDistanceInPigRoad = List(k){List(2){List(k){IntArray(2)} } }
    for (i in 0 until k) {
        val c = edges[pigRoad[i]].third
        for (j in 0 until 2) {
            val start = pigVertices[i][j]
            val distance = minDistance(start, graph)
            for (ti in 0 until k) {
                for (tj in 0 until 2) {
                    minDistanceInPigRoad[i][j][ti][tj] = distance[pigVertices[ti][tj]]
                }
            }
            minDistanceInPigRoad[i][j][i][1 - j] = c
        }
    }
    val minPath = List(1 shl k){List(k){IntArray(2){Int.MAX_VALUE} } }
    for (i in 0 until k) {
        for (j in 0 until 2) {
            val v = pigVertices[i][j]
            minPath[0][i][j] = fromStart[v]
        }
    }
    for (pattern in minPath.indices) {
        for (i in 0 until k) {
            for (j in 0 until 2) {
                val currentDistance = minPath[pattern][i][j] + edges[pigRoad[i]].third
                val nextPattern = pattern or (1 shl i)
                minPath[nextPattern][i][1 - j] = minOf(minPath[nextPattern][i][1 - j], currentDistance)
                for (nextI in 0 until k) {
                    for (nextJ in 0 until 2) {
                        minPath[nextPattern][nextI][nextJ] = minOf(minPath[nextPattern][nextI][nextJ], currentDistance + minDistanceInPigRoad[i][1 - j][nextI][nextJ])
                    }
                }
            }
        }
    }
    var result = Int.MAX_VALUE
    for (i in 0 until k) {
        for (j in 0 until 2) {
            val currentDistance = minPath.last()[i][j]
            val lastVertex = pigVertices[i][j]
            val distance = currentDistance + fromGoal[lastVertex]
            result = minOf(result, distance)
        }
    }
    println(result)
}
0