Untitled

 avatar
unknown
plain_text
a year ago
1.4 kB
3
Indexable
class Solution {
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meet, int fp) {
        vector<vector<pair<int,int>>>adj(n); //time,person
        for(int i=0;i<meet.size();i++){
            int p1=meet[i][0], p2=meet[i][1], t=meet[i][2];
            adj[p1].push_back({t,p2});
            adj[p2].push_back({t,p1});
        }
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; //min meet time on top (time,person)
        pq.push({0,0});
        pq.push({0,fp});

        vector<int>mt(n,INT_MAX); //holds meeting time of all persons
        vector<int>res;

        while(!pq.empty()){ //every node is pushed into the stack will be a part of our result
            auto top=pq.top();
            pq.pop();
            int per=top.second;
            int time=top.first;

            if(mt[per]!=INT_MAX) continue;//since we using BFS if a node has a meeet with a secret holder it must be the lowest time possible

            mt[per]=time;
            res.push_back(per);

            for(auto nbr:adj[per]){
                int p2=nbr.second;
                int t2=nbr.first;
                if(t2>=time){  //the nbrs must have a meet time durinf or after the parent meet time, this is what makes it a hard problem
                pq.push({t2,p2});
                }
                
            }
        }
        return res;
    }
};
Editor is loading...
Leave a Comment