結果

問題 No.1 道のショートカット
コンテスト
ユーザー バカらっく
提出日時 2019-08-29 04:45:53
言語 Kotlin
(2.4.10 + ACL)
コンパイル:
kotlinc -cp /opt/aclib/ac_library.jar _filename_ -include-runtime -d main.jar
実行:
java -cp main.jar:/opt/aclib/ac_library.jar _class_
結果
AC  
実行時間 669 ms / 5,000 ms
+ 539µs
コード長 2,326 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,694 ms
コンパイル使用メモリ 528,680 KB
実行使用メモリ 98,152 KB
最終ジャッジ日時 2026-08-20 06:42:54
合計ジャッジ時間 26,154 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.util.*

fun main(args: Array<String>){
    val cityCount = readLine()!!.toInt()
    val maxMoney = readLine()!!.toInt()
    val roadCount = readLine()!!.toInt()

    val roadStartList = readLine()!!.split(" ").map { it.toInt() }
    val roadToList = readLine()!!.split(" ").map { it.toInt() }
    val roadChargeList = readLine()!!.split(" ").map { it.toInt() }
    val roadTimeList = readLine()!!.split(" ").map { it.toInt() }

    // start, to, Road
    val road = mutableMapOf<Int, MutableMap<Int, MutableList<Road>>>()

    for(i in roadStartList.indices) {
        val startCity = roadStartList[i]
        val toCity = roadToList[i]
        val charge = roadChargeList[i]
        val time = roadTimeList[i]
        if(!road.containsKey(startCity)) {
            road[startCity] = mutableMapOf()
        }
        if(!road[startCity]!!.containsKey(toCity)) {
            road[startCity]!![toCity] = mutableListOf()
        }
        road[startCity]!![toCity]!!.add(Road(charge, time))
    }

    val queue = LinkedList<Task>()

    // city, charge, time
    val map = mutableMapOf<Int, MutableMap<Int, Int>>()

    queue.push(Task(1, 0, 0))
    while (queue.isNotEmpty()) {
        val task = queue.pop()
        if(!map.containsKey(task.location)) {
            map[task.location] = mutableMapOf()
        }
        if(!map[task.location]!!.containsKey(task.subTotalCharge)) {
            map[task.location]!![task.subTotalCharge] = task.time
        } else if(map[task.location]!![task.subTotalCharge]!! > task.time) {
            map[task.location]!![task.subTotalCharge] = task.time
        } else {
            continue
        }
        road[task.location]?.let {
            it.forEach {
                val toCity = it.key
                it.value.forEach{
                    val subCharge = task.subTotalCharge + it.charge
                    val subTotalTime = task.time + it.time
                    if(subCharge <= maxMoney) {
                        queue.push(Task(toCity, subCharge, subTotalTime))
                    }
                }
            }
        }
    }
    map[cityCount]?.let {
        println(it.minBy { it.value }!!.value)
    } ?: run {
        println("-1")
    }
}

class Road(val charge:Int, val time:Int)
class Task(val location:Int, val subTotalCharge:Int, val time:Int)
0