1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance.scala

// There are n cities numbered from 0 to n-1. Given the array edges where 
// edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between 
// cities fromi and toi, and given the integer distanceThreshold.

// Return the city with the smallest number of cities that are reachable through some 
// path and whose distance is at most distanceThreshold, 
// If there are multiple such cities, return the city with the greatest number.

// Notice that the distance of a path connecting cities i and j 
// is equal to the sum of the edges' weights along that path.

// Example 1:
// Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
// Output: 3
// Explanation: The figure above describes the graph. 
// The neighboring cities at a distanceThreshold = 4 for each city are:
// City 0 -> [City 1, City 2] 
// City 1 -> [City 0, City 2, City 3] 
// City 2 -> [City 0, City 1, City 3] 
// City 3 -> [City 1, City 2] 
// Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

// Example 2:
// Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
// Output: 0
// Explanation: The figure above describes the graph. 
// The neighboring cities at a distanceThreshold = 2 for each city are:
// City 0 -> [City 1] 
// City 1 -> [City 0, City 4] 
// City 2 -> [City 3, City 4] 
// City 3 -> [City 2, City 4]
// City 4 -> [City 1, City 2, City 3] 
// The city 0 has 1 neighboring city at a distanceThreshold = 2.
//  
// Constraints:
// 2 <= n <= 100
// 1 <= edges.length <= n * (n - 1) / 2
// edges[i].length == 3
// 0 <= fromi < toi < n
// 1 <= weighti, distanceThreshold <= 10^4
// All pairs (fromi, toi) are distinct.
object Solution {
  def findTheCity(n: Int, edges: Array[Array[Int]], distanceThreshold: Int): Int = {
    val dp = new Array[Array[Int]](n)
    dp.indices foreach {
      dp(_) = new Array[Int](n)
    }
    dp.indices foreach { i =>
      dp(i).indices foreach { j =>
        dp(i)(j) = Int.MaxValue
      }
    }
    edges foreach { case Array(v1, v2, weight) =>
      dp(v1)(v2) = weight
      dp(v2)(v1) = weight
    }

    for { // Floyd Algorithm
      k <- 0 until n
      i <- 0 until n
      j <- 0 until n
      if i != j && dp(i)(k) != Int.MaxValue && dp(k)(j) != Int.MaxValue
    } {
      dp(i)(j) = dp(i)(j) min dp(i)(k) + dp(k)(j)
    }

    dp.indices map { i => i -> dp(i).count(w => w <= distanceThreshold) } reduceLeft {
      (min, cur) =>
        min match {
          case (id, w) => if (cur._2 <= w) cur else min
        }
    } match {
      case (id, _) => id
    }
  }
}