推 JIWP: 你超醜 07/26 15:11
推 mrsonic: 你有什麼用 07/26 15:14
推 dont: 我也忘記用priority queue了QQ 07/26 15:33
→ SydLrio: 你有什麼用 07/26 16:07
題目:
給你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;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.47.70 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721977887.A.7D5.html