1334.阈值距离内邻居最少的城市

Floyd算法计算所有点对之间最短路径。注意先遍历k，才能保证计算k之前，k-1的情况都计算完成了。

时间复杂度：O(N^3)
空间复杂度：O(N^2)

func findTheCity(n int, edges [][]int, distanceThreshold int) int {
    // 构建邻接矩阵
    d := make([][]int, n)

    for i := 0; i < n; i++ {
        d[i] = make([]int, n)
        for j := 0; j < n; j++{
            if i != j {
                d[i][j] = math.MaxInt / 2
            }
        }
    }

    for _, edge := range edges {
        x := edge[0]
        y := edge[1]
        z := edge[2]

        d[x][y] = z
        d[y][x] = z
    }

    // Floyd算法
    // d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    // 注意先遍历k，才能保证计算k之前，k-1的情况都计算完成了
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if k != i && k != j {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                }
            }
        }
    }

    // fmt.Printf("d[i][j]: %v\n", d)

    minNeighboor := math.MaxInt / 2
    ans := 0

    for i := 0; i < n; i++ {
        neighboor := 0
        for j := 0; j < n; j++ {
            if i != j && d[i][j] <= distanceThreshold {
                neighboor++
            }
        }
        if neighboor < minNeighboor || (neighboor == minNeighboor && i > ans) {
            minNeighboor = neighboor
            ans = i
        }
    }

    return ans

}

func min(a, b int) int {
    if (a > b){
        return b
    }
    return a
}