Untitled
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