Leetcode 1334. 阈值距离内邻居最少的城市 Dijkstra/Floyd

原题链接：Leetcode 1334. 阈值距离内邻居最少的城市

Dijkstra

class Solution {
public:vector<vector<pair<int,int>>> adj;vector<int> visit;vector<int> dis;void dijkstra(int n,int d){dis[d]=0;for(int i=0;i<n;i++){int u=-1,MINDIS=INT_MAX;for(int j=0;j<n;j++){if(!visit[j] && dis[j]<MINDIS){u=j; MINDIS=dis[j];}} if(u==-1) return ;visit[u]=1;for(auto x:adj[u]){if(!visit[x.first] && dis[u]+x.second<dis[x.first]){dis[x.first]=dis[u]+x.second;}}}}int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {adj.resize(n);visit.resize(n);dis.resize(n,INT_MAX);for(auto x:edges){adj[x[0]].push_back({x[1],x[2]});adj[x[1]].push_back({x[0],x[2]});}int res=-1,tmp=INT_MAX;for(int i=0;i<n;i++){for(int j=0;j<n;j++){visit[j]=0;dis[j]=INT_MAX;}dijkstra(n,i);int num=0;for(int j=0;j<n;j++){if(dis[j]<=distanceThreshold && i!=j) num++;}if(num<=tmp){tmp=num; res=i;}}return res;}
};

Floyd

class Solution {
public:int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {vector<vector<int>> d(n,vector<int>(n,INT_MAX));for(auto x:edges){d[x[0]][x[1]]=x[2];d[x[1]][x[0]]=x[2];}for(int i=0;i<n;i++) d[i][i]=0;for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(d[i][k]!=INT_MAX && d[k][j]!=INT_MAX && d[i][k]+d[k][j]<d[i][j]){d[i][j]=d[i][k]+d[k][j];}}}}int res=-1,tmp=INT_MAX;for(int i=0;i<n;i++){int num=0;for(int j=0;j<n;j++){if(d[i][j]<=distanceThreshold && i!=j) num++;}if(num<=tmp){tmp=num;res=i;}}return res;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！