findCityFloydWarshall1334

fun findTheCity(n: Int, edges: Array<IntArray>, distanceThreshold: Int): Int {

    val graphArr = Array(n){
        IntArray(n)
    }


    for (i in 0 until n) {
        Arrays.fill(graphArr[i], Int.MAX_VALUE)
        graphArr[i][i] = 0
    }


    for(edge in edges){
        val source: Int = edge[0]
        val target: Int =  edge[1]
        val weight: Int = edge[2]

        graphArr[source][target] = weight
        graphArr[target][source] = weight
    }

    calculateAllPairShortestPath(n, graphArr)

    var maxVisits = n+1 // max possible
    var result= -1 //worst case, no city found

    for (i in 0 until n) {
        var visit = 0
        for (j in 0 until n) {
            if ( graphArr[i][j] <= distanceThreshold)//city within the our threshold value
                visit++
        }
        if (visit <= maxVisits){//updating the minimum city count vertex every time
            maxVisits = minOf(maxVisits, visit )
            result = i
        }
    }
    return result
}

fun calculateAllPairShortestPath(n: Int, graphArr: Array<IntArray>){
    for(k in 0 until n){
        for(i in 0 until n){
            for(j in 0 until n){
                graphArr[i][j] = minOf(graphArr[i][j], (graphArr[i][k]+ graphArr[k][j] ))
            }
        }
    }