結果

問題 No.1 道のショートカット
コンテスト
ユーザー バカらっく
提出日時 2019-08-29 04:45:53
言語 Kotlin
(2.1.0)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
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