Re: [閒聊] 每日LeetCode
原本用map寫會超時
後來看別人用pq
換個思路重寫一個
2092. Find All People With Secret
class Solution {
public:
#define p pair<int, int>
vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int
firstPerson) {
vector<pair<int,int>> adj[n];
for (auto it : meetings) {
adj[it[0]].push_back({it[1],it[2]});
adj[it[1]].push_back({it[0],it[2]});
}
priority_queue<p, vector<p>, greater<p> > pq;
pq.push({0, 0});
pq.push({0, firstPerson});
vector<int> vis(n, 0);
while (!pq.empty()) {
auto it = pq.top();
int time=it.first;
int person=it.second;
pq.pop();
if (vis[person]) {
continue;
}
vis[person]++;
for (auto it : adj[person]) {
if (!vis[it.first] && it.second >= time) {
pq.push({it.second, it.first});
}
}
}
vector<int> ans;
for (int i = 0; i < n; ++i) {
if (vis[i]) {
ans.push_back(i);
}
}
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.149.184 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708776325.A.2CA.html
推
02/24 20:06,
3月前
, 1F
02/24 20:06, 1F
→
02/24 20:07,
3月前
, 2F
02/24 20:07, 2F
推
02/24 20:11,
3月前
, 3F
02/24 20:11, 3F
→
02/24 20:36,
3月前
, 4F
02/24 20:36, 4F
討論串 (同標題文章)
完整討論串 (本文為第 715 之 719 篇)：
閒聊
1
3