結果

問題 No.1812 Uribo Road
ユーザー yudedakoyudedako
提出日時 2022-01-25 20:09:36
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,178 ms / 5,000 ms
コード長 3,029 bytes
コンパイル時間 18,558 ms
コンパイル使用メモリ 469,228 KB
実行使用メモリ 96,692 KB
最終ジャッジ日時 2024-12-17 15:08:58
合計ジャッジ時間 44,621 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 341 ms
60,608 KB
testcase_01 AC 338 ms
60,436 KB
testcase_02 AC 340 ms
60,572 KB
testcase_03 AC 463 ms
66,516 KB
testcase_04 AC 340 ms
60,280 KB
testcase_05 AC 337 ms
60,568 KB
testcase_06 AC 338 ms
60,568 KB
testcase_07 AC 444 ms
64,476 KB
testcase_08 AC 509 ms
67,132 KB
testcase_09 AC 523 ms
66,904 KB
testcase_10 AC 503 ms
64,772 KB
testcase_11 AC 446 ms
63,000 KB
testcase_12 AC 1,150 ms
95,744 KB
testcase_13 AC 980 ms
95,244 KB
testcase_14 AC 897 ms
95,764 KB
testcase_15 AC 842 ms
87,572 KB
testcase_16 AC 884 ms
93,200 KB
testcase_17 AC 1,146 ms
96,552 KB
testcase_18 AC 975 ms
81,792 KB
testcase_19 AC 1,178 ms
96,672 KB
testcase_20 AC 1,162 ms
96,692 KB
testcase_21 AC 1,168 ms
96,364 KB
testcase_22 AC 1,111 ms
96,580 KB
testcase_23 AC 520 ms
64,848 KB
testcase_24 AC 359 ms
60,692 KB
testcase_25 AC 718 ms
79,040 KB
testcase_26 AC 424 ms
60,768 KB
testcase_27 AC 892 ms
79,300 KB
testcase_28 AC 796 ms
84,680 KB
testcase_29 AC 347 ms
60,608 KB
testcase_30 AC 615 ms
67,784 KB
testcase_31 AC 1,130 ms
91,540 KB
testcase_32 AC 480 ms
64,728 KB
testcase_33 AC 1,055 ms
95,716 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