题目:
给你n个节点
给你一堆路径
给你一个distance 的上限
请问对于一个节点
不走超过距离上限 能到的节点数量
最少的是哪一个节点
思路:
原本想要dfs
然后发现要记录走过的地方
不然会一直重复走
但是纪录走过的地方会有更好的路径出现
然后却不能走的情况
所以不行
然后改成对每个节点dijk
然后看能走到哪里
在统计一下就好了了
我没用priority queue写
因为我忘了要用了= =
所以超丑
嘿嘿嘿
class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold)
{
int len = edges.size();
unordered_map<int,vector<pair<int,int>>> paper;
int dislim;
dislim = distanceThreshold;
for(int i = 0 ; i < len ; i ++)
{
if(edges[i][2]>distanceThreshold)continue;
paper[edges[i][0]].push_back({edges[i][1] , edges[i][2]});
paper[edges[i][1]].push_back({edges[i][0] , edges[i][2]});
}
vector<int> all(n,0);
for(int i = 0 ; i < n ; i ++)
{
vector<int> now(n,INT_MAX);
int ok = 1;
now[i] = 0;
while(ok)
{
ok = 0;
for(int j = 0 ; j < n ; j ++)
{
if(now[j] != INT_MAX)
{
for(auto k : paper[j] )
{
if(now[j] + k.second <= dislim)
{
if(now[j] + k.second < now[k.first])
{
now[k.first] = now[j] + k.second;
ok = 1;
}
}
}
}
}
}
for(int p = 0 ; p < n ; p ++)
{
if(now[p] <= dislim)
{
all[p] ++;
}
}
}
int res = 0;
int ress = all[0];
for(int i = 1 ; i < n ; i ++)
{
if(all[i] <= ress)
{
res = i;
ress=all[i];
}
}
return res;
}
};