[白俊]1657号タイムマシン

11151 ワード
ベルマンフォード テキストリンク
白俊-11657タイムマシン
質問する
N都市があります.もう一つの都市から別の都市へ行くバスはM台あります.バスごとにA、B、Cで表すことができます.Aは起点都市で、Bは到着都市で、Cはバスで移動するのに必要な時間です.時間Cが正数でない場合がある.C=0は瞬間移動を表し、C<0は時間がタイムマシンに戻ることを表す.
1番都市から出発して、1つのプログラムを編制して、残りの都市の最も速い時間を求めます.
方法
これは都市ごとに最も速い時間の問題なので、ダエストラとベルマンフォードが考えられます.
幹線に負の値が存在するため,ベルマンフォードを用いて解いた.
少なくともN−1に幹線N−1本があるため、ベルマンフォードは頂点をN回繰り返した.したがって,N回目に値を更新すると負数ループが発生したといえるため,N回繰り返す.
コード#コード#
class IO11657 {
    private val br = System.`in`.bufferedReader()
    private val bw = System.out.bufferedWriter()

    fun getNM() = br.readLine().split(" ").map { it.toInt() }
    fun getRow() = br.readLine().split(" ").map { it. toInt() }
    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
}

fun main() {
    val io = IO11657()
    val (N, M) = io.getNM()
    val arr = Array(M) { io.getRow() }
    val distance = Array(N + 1) { Long.MAX_VALUE }
    var flag = false

    distance[1] = 0

    for (i in 1..N) {
        for (j in 0 until M) {
            val (curNode, nextNode, cost) = arr[j]

            if (distance[curNode] != Long.MAX_VALUE && distance[nextNode] > distance[curNode] + cost) {
                distance[nextNode] = distance[curNode] + cost
                if ( i == N ) {
                    flag= true
                }
            }
        }
    }

    if (flag) {
        io.write( (-1).toString())
        io.close()
    } else {
        for (idx in 2..N) {
            if (distance[idx] == Long.MAX_VALUE) {
                io.write("-1\n")
            } else {
                io.write("${distance[idx]}\n")
            }
        }
        io.close()
    }

}
nextjs devサーバビルダー(AWSライト付き)
PackageManagerServiceスキャンインストールapkの詳細