[Leetcode] 3112. Minimum Time to Visit Disappearing Nodes

https://leetcode.com/problems/minimum-time-to-visit-disappearing-nodes/description/

다익스트라 문제인데 일정 시간이 지나면 노드가 사라진다.

다익스트라 코드 기반으로 노드까지 갔을 때 시간이 사라지는 시간보다 빠르면 이라는 조건을 추가했따.

from heapq import heappush, heappop
from collections import defaultdict

class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        dist = [-1] * n
        dist[0] = 0

        graph = defaultdict(list)

        for e in edges:
            u, v, length = e
            graph[u].append((v, length))
            graph[v].append((u, length))

        for i in range(n):
            for j in range(i+1, n):
                graph

        q = [(0, 0)]
        cost = 0

        while q:
            cost, idx = heappop(q)

            if 0 <= dist[idx] < cost:
                continue

            for adj, d in graph[idx]:        
                if (dist[adj] == -1 or dist[adj] > cost + d) and disappear[adj] > cost + d:
                    dist[adj] = cost + d
                    heappush(q, (dist[adj], adj))
        
        return dist

그리고 시간초과가 났다.
50,000개짜리 노드를 가진 그래프를 탐색하면서 시간초과가 났다. 왜지......

코드 중간에 쓸데없는 for문이 있었다. 문제를 이해하는 과정에서 써놓고 안 뺐다;;;

from heapq import heappush, heappop
from collections import defaultdict

class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        dist = [-1] * n
        dist[0] = 0

        graph = defaultdict(list)

        for e in edges:
            u, v, length = e
            graph[u].append((v, length))
            graph[v].append((u, length))

        q = [(0, 0)]
        cost = 0

        while q:
            cost, idx = heappop(q)

            if 0 <= dist[idx] < cost:
                continue

            for adj, d in graph[idx]:        
                if (dist[adj] == -1 or dist[adj] > cost + d) and disappear[adj] > cost + d:
                    dist[adj] = cost + d
                    heappush(q, (dist[adj], adj))
        
        return dist

이렇게 해주니까 통과했다.