leetocde 5941. 找出知晓秘密的所有专家

 1 typedef pair<int,int> pii;
 2 const int N=1e5+5;
 3 class Solution {
 4 public:
 5     struct cmp{
 6         bool operator()(pii &a, pii &b)
 7         {
 8             return a.second>b.second;
 9         }
10     };
11     
12     int dis[N];
13     vector<int> findAllPeople(int n, vectorint>>& meetings, int firstPerson) {
14         memset(dis,0x3f,sizeof(dis));
15         vectorG[N];
16         vector<int>ans;
17         priority_queue,cmp>pq;
18         for(auto &p:meetings)
19         {
20             int u=p[0],v=p[1],d=p[2];
21             G[u].push_back({v,d});
22             G[v].push_back({u,d});
23         }
24         dis[0]=0;
25         G[0].push_back({firstPerson,0});
26         pq.push({0,0});
27         while(pq.size())
28         {
29             auto [u,d]=pq.top();
30             pq.pop();
31             if(dis[u]continue;
32             ans.push_back(u);
33             for(auto &[v,dv]:G[u])
34             {
35                if(dv>=d&&dv<dis[v])
36                {
37                    pq.push({v,dv});
38                    dis[v]=dv;
39                }
40             }
41         }
42         return ans;
43     }
44 };

这是dijkstra的变形题，关键在于能否看出用两个专家的时间代替距离，这样更新的时候我们判断一下当前节点的所有dis[u]与当前时间线d的关系，dis[u]=d，说明v的时间线在d后面，从而v也是能获取信息的，否则v在当前d的前面v是不能知道信息的，由dij算法原理，我们知道每个专家u的d是它知道信息的最开始时间。从而算法是正确的。

 1 typedef pair<int,int> pii;
 2 class Solution {
 3 public:
 4 
 5     vector<int> findAllPeople(int n, vectorint>>& meetings, int firstPerson) {
 6         vector<int>ans;
 7         int f[n];
 8         memset(f,0,sizeof(f));
 9         f[0]=1;f[firstPerson]=1;
10         map<int,vector>mp;
11         for(auto &p:meetings)
12         {
13             int u=p[0],v=p[1],time=p[2];
14             mp[time].push_back({u,v});
15         }  
16         for(auto &t:mp)
17         {
18             unordered_map<int,vector<int>>G;
19             map<int,int>m;
20             for(auto &[u,v]:t.second)
21             {
22                 G[u].push_back(v);
23                 G[v].push_back(u);
24                 m[u]=1;m[v]=1;               
25             }
26             queue<int>q;
27             for(auto &p:m)
28             {
29                 if(f[p.first])
30                 q.push(p.first);
31             }
32             while(q.size())
33             {
34                 auto u=q.front();
35                 q.pop();
36                 for(auto &v:G[u])
37                 {
38                     if(!f[v])
39                     {
40                         q.push(v);
41                         f[v]=1;
42                     }
43                 }
44             }
45         }
46         for(int i=0;iif(f[i])ans.push_back(i);
47         return ans;
48     }
49 };

图的做法复杂度好高啊，也是我一开始先预处理；