フロイド・ウォーシャル最短経路アルゴリズムのエラー

Question

問題文：https://www.hackerrank.com/challenges/floyd-city-of-blinding-lights

コード：

import scala.io.StdIn._ 
import scala.collection.mutable 
object Solution { 
    def FloydWarshall(n: Int, adj: Array[Array[Int]]): Array[Array[Int]] = { 
     val distance: Array[Array[Int]] = adj 
     for(k <- 0 until n){ 
      for(u <- 0 until n){ 
       for(v <- 0 until n){ 
        distance(u)(v) = minimum(distance(u)(v), distance(u)(k) + distance(k)(v)) 
       } 
      } 
     } 
     distance 
    } 

    def minimum(a: Int, b: Int):Int = { 
     if(a < b){ 
      a 
     } else { 
      b 
     } 
    } 

    def main(args: Array[String]) { 
     var input: Array[Int] = readLine().split(" ").map(_.toInt) 
     val n: Int = input(0) 
     val m: Int = input(1)  
     val adj: Array[Array[Int]] = Array.fill(n, n)(351) 

     for(_ <- 1 to m){ 
      input = readLine().split(" ").map(_.toInt) 
      val u: Int = input(0) 
      val v: Int = input(1) 
      val w: Int = input(2) 
      adj(u-1)(v-1) = w 
     } 

     for(i <- 0 until n){ 
      adj(i)(i) = 0 
     } 

     val q: Int = readInt() 
     val distance: Array[Array[Int]] = FloydWarshall(n, adj) 
     val results: mutable.ListBuffer[Int] = mutable.ListBuffer[Int]() 
     for(_ <- 1 to q) { 
      input = readLine().split(" ").map(_.toInt) 
      val u: Int = input(0) 
      val v: Int = input(1) 
      val result: Int = if(distance(u-1)(v-1) == 351) -1 else distance(u-1)(v-1)  
      results += result 
     } 
     println(results.mkString("\n")) 
    } 
} 

失敗テストケース：

入力：https://paste.ubuntu.com/24406100/

出力：https://paste.ubuntu.com/24406106/

これをあなたはeは失敗したテストケースのみであり、私は自分のコードで問題を把握することができません。

EDIT：@qwertymanが指摘しているように、2つのエッジまたはモードエッジを持つ最短パスが351を超えます。この問題の正しい無限値はMaxEdgeWeight * MaxNodes-1 + 1 = 350 *（ 400-1）+ 1

固定コード：

import scala.io.StdIn._ 
import scala.collection.mutable 
import util.control.Breaks._ 
object Solution { 
    def FloydWarshall(n: Int, adj: Array[Array[Int]]): Array[Array[Int]] = { 
     val distance: Array[Array[Int]] = adj 
     for(k <- 0 until n){ 
      for(u <- 0 until n){ 
       for(v <- 0 until n){ 
         distance(u)(v) = minimum(distance(u)(v), distance(u)(k) + distance(k)(v))  
       } 
      } 
     } 
     distance 
    } 

    def minimum(a: Int, b: Int):Int = { 
     if(a < b){ 
      a 
     } else { 
      b 
     } 
    } 

    def main(args: Array[String]) { 
     var input: Array[Int] = readLine().split(" ").map(_.toInt) 
     val n: Int = input(0) 
     val m: Int = input(1) 
     val infinity: Int = 350 * 399 + 1// maximum shortest path N-1 edges 
     val adj: Array[Array[Int]] = Array.fill(n, n)(infinity) 

     for(_ <- 1 to m){ 
      input = readLine().split(" ").map(_.toInt) 
      val u: Int = input(0) - 1 
      val v: Int = input(1) - 1 
      val w: Int = input(2) 
      adj(u)(v) = w 
     } 

     for(i <- 0 until n){ 
      adj(i)(i) = 0 
     } 

     val q: Int = readInt() 
     val distance: Array[Array[Int]] = FloydWarshall(n, adj) 
     val results: mutable.ListBuffer[Int] = mutable.ListBuffer[Int]() 
     for(_ <- 1 to q) { 
      input = readLine().split(" ").map(_.toInt) 
      val u: Int = input(0) - 1 
      val v: Int = input(1) - 1 
      val result: Int = if(distance(u)(v) == infinity) -1 else distance(u)(v) 
      results += result 
     } 
     println(results.mkString("\n")) 
    } 
} 

Answer 1

プログラムが問題のようです無効な距離のためのマーカーとして値351を使用しています。

各エッジの最大重みは350であることが分かっていますが、2つ以上のエッジからなるパスによっても値351の距離にはまだ到達できます。