結果

問題 No.1812 Uribo Road
ユーザー yudedakoyudedako
提出日時 2022-01-25 20:09:36
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,161 ms / 5,000 ms
コード長 3,029 bytes
コンパイル時間 16,966 ms
コンパイル使用メモリ 435,100 KB
実行使用メモリ 67,524 KB
最終ジャッジ日時 2023-08-22 15:34:57
合計ジャッジ時間 42,716 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 313 ms
57,384 KB
testcase_01 AC 312 ms
57,300 KB
testcase_02 AC 313 ms
57,292 KB
testcase_03 AC 440 ms
61,212 KB
testcase_04 AC 308 ms
57,232 KB
testcase_05 AC 311 ms
57,124 KB
testcase_06 AC 310 ms
57,008 KB
testcase_07 AC 414 ms
61,172 KB
testcase_08 AC 478 ms
61,332 KB
testcase_09 AC 488 ms
61,248 KB
testcase_10 AC 470 ms
61,584 KB
testcase_11 AC 415 ms
57,524 KB
testcase_12 AC 1,018 ms
64,488 KB
testcase_13 AC 927 ms
64,968 KB
testcase_14 AC 897 ms
65,984 KB
testcase_15 AC 855 ms
63,892 KB
testcase_16 AC 821 ms
66,136 KB
testcase_17 AC 1,081 ms
66,252 KB
testcase_18 AC 966 ms
64,840 KB
testcase_19 AC 1,161 ms
67,524 KB
testcase_20 AC 1,147 ms
67,120 KB
testcase_21 AC 1,144 ms
67,388 KB
testcase_22 AC 1,153 ms
66,984 KB
testcase_23 AC 492 ms
61,316 KB
testcase_24 AC 329 ms
57,148 KB
testcase_25 AC 670 ms
63,792 KB
testcase_26 AC 384 ms
57,848 KB
testcase_27 AC 770 ms
64,264 KB
testcase_28 AC 736 ms
63,816 KB
testcase_29 AC 315 ms
57,116 KB
testcase_30 AC 558 ms
64,180 KB
testcase_31 AC 1,122 ms
65,000 KB
testcase_32 AC 446 ms
61,488 KB
testcase_33 AC 1,053 ms
64,760 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