結果

問題 No.1812 Uribo Road
ユーザー yudedakoyudedako
提出日時 2022-01-25 20:09:36
言語 Kotlin
(2.1.0)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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