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

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

题解

很明显，本题是一道最短路径问题。对于单源最短路径问题，可以使用Dijkstra算法。但是本题是一道完全的最短路径问题。因此有两种解决方案，一种是使用n个Dijkstra分别计算每个节点的单源最短路。第二种是使用Floyd算法。
Floyd算法是一种典型的动态规划算法，对于每一个节点k都检查dis[i][k] + dis[k][j] < dis[i][j]，如果成立的话则进行更新。在更新k+1时，d[i][k+1]也已经是经过k进行更新后的结果。因此当对每个节点都完成更新后，所得到的矩阵就是最短路矩阵。
具体代码实现如下：

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<int> t (n, 1000000);
        vector<vector<int>> G(n, t);
        for(int i=0;i<edges.size();i++)
        {
            G[edges[i][0]][edges[i][1]] = edges[i][2];
            G[edges[i][1]][edges[i][0]] = edges[i][2];
        }
        
        for(int k=0;k<n;k++)
        {
            for(int i=0;i<n;i++)
            {
                if(i != k)
                {
                    for(int j=i+1;j<n;j++)
                    {
                        if(j == k)
                        {
                            continue;
                        }
                        if(G[i][k] + G[k][j] < G[i][j])
                        {
                            G[i][j] = G[i][k] + G[k][j];
                            G[j][i] = G[i][k] + G[k][j];
                        }
                    }
                }
            }
        }
        int min = 10000;
        int imin = -1;
        for(int i=0;i<n;i++)
        {
            int count = 0;
            for(int j=0;j<n;j++)
            {
                cout<<G[i][j]<<" ";
                if(distanceThreshold >= G[i][j])
                {
                    count++;
                }
            }
            if(min >= count)
            {
                min = count;
                imin = i;
            }
            cout<<endl;
        }
        return imin;
    }
};