[Leetcode] 743. Network Delay Time

 

문제

 

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. if it is impossible for all the n nodes to receive the signal, return -1.

 

 

n개의 노드로 구성된 1부터 n까지의 레이블이 지정된 네트워크가 제공됨. 또한 시간, 이동 시간 목록이 지정된 에지 시간[i] = (ui, vi, wi)이며, 여기서 ui는 소스 노드(출발 노드), vi는 대상 노드(도착 노드), wi는 신호가 소스에서 타겟으로 이동하는 데 걸리는 시간(가중치)입니다.

주어진 노드 k로부터 신호를 보낼 것. 모든 n개의 노드가 신호를 받는 데 걸리는 최소 시간을 반환하라. 하나의 노드라도 도달하지 못한다면 -1를 반환하라

 

제약 조건

 

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

 

 

 

입출력 예시

 

1. Example 1

 

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

 

 

2. Example 2

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

 

 

 

 

풀이

import heapq
import sys
from collections import defaultdict


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # dict의 원소의 기본형은 list라고 지정
        # 그래프 생성
        graph = defaultdict(list)
        print("g:", graph)
        for time in times:
            # u, v, w 넣기
            graph[time[0]].append((time[2], time[1]))

        costs = {}
        pq = []
        heapq.heappush(pq, (0, k))

        while pq:
            cur_cost, cur_node = heapq.heappop(pq)
            # 방문했는지 확인
            if cur_node not in costs:
                costs[cur_node] = cur_cost
                for cost, next_node in graph[cur_node]:
                    next_cost = cur_cost + cost
                    print("nc:", next_cost)
                    heapq.heappush(pq, (next_cost, next_node))

        # 방문 못한 노드 찾기
        for node in range(1, n+1):
            if node not in costs:
                return -1
        print("최소값들:", costs.values())
        return max(costs.values())

 

 

 

 

 

https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode