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

Dijstra

class Solution {
public:
    int djistkra(int k,int n,vector<vector<int>> &g,int distanceThreshold){
        vector<int>dist(n,INT_MAX/2);
        dist[k]=0;//从k开始
        vector<bool>used(n,false);
        for(int i=0;i<n;i++){
            int t=-1;
            for(int j=0;j<n;j++){
                if(!used[j]&&(t==-1||dist[j]<dist[t]))t=j;//找到最小距离的点
            }
            used[t]=true;
            for(int u=0;u<n;u++){
                dist[u]=min(dist[u],dist[t]+g[t][u]);//更新
            }
        }
        int cnt=0;
        for(int i=0;i<n;i++)if(dist[i]<=distanceThreshold)cnt++;//统计相邻距离小于阈值的城市
        return cnt;
    }
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        int ans=0;
        int inf=INT_MAX/2;
        vector<vector<int>> g(n,vector<int>(n,inf));
        for(auto e:edges){
            g[e[0]][e[1]]=e[2];
            g[e[1]][e[0]]=e[2];
        }
        int cur=n;
        for(int i=0;i<n;i++){
            int x=djistkra(i,n,g,distanceThreshold);
            if(x<=cur){
                cur=x;
                ans=i;
            }
        }
        return ans;
    }
};

Floyd

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        
        int inf=INT_MAX/2;
        vector<vector<int>> g(n,vector<int>(n,inf));
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(i==j)g[i][j]=0;
        for(auto e:edges){
            g[e[0]][e[1]]=e[2];
            g[e[1]][e[0]]=e[2];
        }
        for(int k=0;k<n;k++)
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
        int ans=INT_MAX;
        int mincnt=INT_MAX;
        for(int i=0;i<n;i++){
            int cnt=0;
            for(int j=0;j<n;j++){
                 if(g[i][j]<=distanceThreshold)cnt++;
             }
            if(cnt<=mincnt){
                mincnt=cnt;
                ans=i;
            }
        }
        return ans;
    }
};