lc 2092

https://leetcode.com/problems/find-all-people-with-secret/
mail@pastecode.io avatar
unknown
python
2 years ago
733 B
13
Indexable
Never
class Solution:
    def findAllPeople(self, n: int, A: List[List[int]], fp: int) -> List[int]:
        A.append((0,fp,0))
        times = defaultdict(list)
        for x,y,t in A:
            times[t].append((x,y))
        G = [[] for _ in range(n)]
        for t in sorted(times.keys()):
            for x,y in times[t]:
                G[x].append((t, y))
                G[y].append((t, x))
        dis = [inf]*n; dis[0] = 0 
        q = [(0, 0)]
        while q:
            t, u = heappop(q)
            if t > dis[u]: continue
            for vt, v in G[u]:
                if vt >= t and dis[v] > vt:
                    heappush(q, (vt, v))
                    dis[v] = vt
        return [ i for i in range(n) if inf!=dis[i]]