What is the best way to solve Network Delay Time?

The optimized O(1) approach using Advanced Graphs patterns is generally preferred.

상위 150개 인터뷰쉬움

네트워크 지연 시간

'네트워크 지연 시간' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

1부터 n까지 레이블이 지정된 n개의 노드로 구성된 네트워크가 제공됩니다. 또한 방향이 지정된 간선으로 이동 시간 목록인 시간이 제공됩니다. times[i] = [ui, vi, wi], 여기서 ui는 소스 노드, vi는 대상 노드, wi는 신호가 소스에서 대상으로 이동하는 데 걸리는 시간입니다.

주어진 노드 k에서 신호를 보냅니다. n개 노드 모두가 신호를 수신하는 데 걸리는 최소 시간을 반환합니다. n개의 노드 모두가 신호를 수신하는 것이 불가능하면 -1을 반환합니다.

networkDelayTime(times: List[List[int]], n: int, k: int) -> int 함수를 작성하세요.

제약

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

예

Example 1

Input

times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Output

Explanation

The signal starts at node 2. It reaches 1 and 3 in 1 unit of time, and 4 in 2 units of time.

Example 2

Input

times = [[1,2,1]], n = 2, k = 1

Output

Explanation

Signal reaches node 2 from node 1 in 1 unit of time.

Example 3

Input

times = [[1,2,1]], n = 2, k = 2

Output

-1

Explanation

Signal starts at node 2, but there is no path from node 2 to node 1. So node 1 never receives it.

Need a Hint?

세트나 힙과 같은 고급 그래프 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

고급 그래프 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(1)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def network_delay_time_opt(times, n, k):
    return network_delay_time_brute(times, n, k)

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

import heapq, collections
def network_delay_time_brute(times, n, k):
    edges = collections.defaultdict(list)
    for u, v, w in times: edges[u].append((v, w))
    min_heap = [(0, k)]
    visit = {}
    while min_heap:
        w1, n1 = heapq.heappop(min_heap)
        if n1 in visit: continue
        visit[n1] = w1
        for n2, w2 in edges[n1]:
            if n2 not in visit: heapq.heappush(min_heap, (w1 + w2, n2))
    return max(visit.values()) if len(visit) == n else -1