Re: [閒聊] 每日LeetCode

[wu10200512 (廷廷)]

原本用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
推 Che31128: 大師
→ JIWP: 大師
推 sustainer123: 大師
→ DJYOSHITAKA: 大師 我放推了