結果

問題 No.1 道のショートカット
ユーザー バカらっくバカらっく
提出日時 2019-08-29 04:45:53
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 948 ms / 5,000 ms
コード長 2,326 bytes
コンパイル時間 18,444 ms
コンパイル使用メモリ 429,568 KB
実行使用メモリ 67,368 KB
最終ジャッジ日時 2023-09-27 22:23:30
合計ジャッジ時間 37,323 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 263 ms
52,992 KB
testcase_01 AC 266 ms
52,728 KB
testcase_02 AC 268 ms
53,088 KB
testcase_03 AC 270 ms
52,820 KB
testcase_04 AC 268 ms
53,500 KB
testcase_05 AC 272 ms
53,168 KB
testcase_06 AC 281 ms
53,072 KB
testcase_07 AC 271 ms
52,976 KB
testcase_08 AC 398 ms
60,596 KB
testcase_09 AC 331 ms
53,140 KB
testcase_10 AC 378 ms
60,356 KB
testcase_11 AC 548 ms
65,816 KB
testcase_12 AC 533 ms
63,280 KB
testcase_13 AC 544 ms
62,796 KB
testcase_14 AC 280 ms
52,904 KB
testcase_15 AC 271 ms
52,764 KB
testcase_16 AC 295 ms
52,868 KB
testcase_17 AC 267 ms
53,076 KB
testcase_18 AC 281 ms
53,156 KB
testcase_19 AC 289 ms
53,132 KB
testcase_20 AC 326 ms
55,584 KB
testcase_21 AC 294 ms
52,996 KB
testcase_22 AC 287 ms
52,928 KB
testcase_23 AC 847 ms
67,112 KB
testcase_24 AC 948 ms
67,368 KB
testcase_25 AC 471 ms
61,856 KB
testcase_26 AC 374 ms
59,956 KB
testcase_27 AC 566 ms
67,276 KB
testcase_28 AC 274 ms
53,024 KB
testcase_29 AC 463 ms
62,480 KB
testcase_30 AC 303 ms
53,028 KB
testcase_31 AC 451 ms
60,856 KB
testcase_32 AC 474 ms
64,784 KB
testcase_33 AC 337 ms
55,296 KB
testcase_34 AC 605 ms
63,860 KB
testcase_35 AC 320 ms
54,964 KB
testcase_36 AC 337 ms
53,240 KB
testcase_37 AC 323 ms
53,516 KB
testcase_38 AC 282 ms
52,832 KB
testcase_39 AC 293 ms
53,108 KB
testcase_40 AC 298 ms
53,388 KB
testcase_41 AC 288 ms
52,840 KB
testcase_42 AC 277 ms
52,908 KB
testcase_43 AC 270 ms
52,896 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