結果

問題 No.1 道のショートカット
ユーザー バカらっくバカらっく
提出日時 2019-08-29 04:45:53
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,142 ms / 5,000 ms
コード長 2,326 bytes
コンパイル時間 17,374 ms
コンパイル使用メモリ 453,960 KB
実行使用メモリ 94,408 KB
最終ジャッジ日時 2024-07-20 16:43:00
合計ジャッジ時間 39,692 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 319 ms
51,628 KB
testcase_01 AC 314 ms
51,648 KB
testcase_02 AC 332 ms
51,728 KB
testcase_03 AC 320 ms
51,804 KB
testcase_04 AC 320 ms
51,760 KB
testcase_05 AC 324 ms
51,612 KB
testcase_06 AC 330 ms
51,772 KB
testcase_07 AC 329 ms
51,468 KB
testcase_08 AC 470 ms
59,124 KB
testcase_09 AC 388 ms
52,700 KB
testcase_10 AC 442 ms
58,244 KB
testcase_11 AC 650 ms
73,468 KB
testcase_12 AC 645 ms
74,464 KB
testcase_13 AC 641 ms
74,192 KB
testcase_14 AC 331 ms
51,964 KB
testcase_15 AC 316 ms
51,744 KB
testcase_16 AC 342 ms
51,972 KB
testcase_17 AC 319 ms
51,776 KB
testcase_18 AC 336 ms
51,904 KB
testcase_19 AC 342 ms
51,992 KB
testcase_20 AC 393 ms
53,144 KB
testcase_21 AC 350 ms
51,832 KB
testcase_22 AC 354 ms
51,836 KB
testcase_23 AC 1,049 ms
93,652 KB
testcase_24 AC 1,142 ms
94,408 KB
testcase_25 AC 572 ms
63,140 KB
testcase_26 AC 446 ms
59,280 KB
testcase_27 AC 699 ms
93,380 KB
testcase_28 AC 331 ms
51,636 KB
testcase_29 AC 557 ms
62,108 KB
testcase_30 AC 368 ms
52,268 KB
testcase_31 AC 541 ms
61,512 KB
testcase_32 AC 557 ms
64,956 KB
testcase_33 AC 416 ms
53,456 KB
testcase_34 AC 855 ms
84,104 KB
testcase_35 AC 373 ms
52,396 KB
testcase_36 AC 403 ms
52,896 KB
testcase_37 AC 394 ms
52,564 KB
testcase_38 AC 331 ms
51,660 KB
testcase_39 AC 335 ms
51,964 KB
testcase_40 AC 349 ms
52,308 KB
testcase_41 AC 339 ms
51,640 KB
testcase_42 AC 317 ms
51,612 KB
testcase_43 AC 322 ms
51,652 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:3:10: warning: parameter 'args' is never used
fun main(args: Array<String>){
         ^
Main.kt:6:9: warning: variable 'roadCount' is never used
    val roadCount = readLine()!!.toInt()
        ^
Main.kt:62:38: warning: unnecessary non-null assertion (!!) on a non-null receiver of type Map.Entry<Int, Int>
        println(it.minBy { it.value }!!.value)
                                     ^

ソースコード

diff #

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