LeetCode 743: Network Delay Time ·

基本資料
#

難易度: medium 第一次嘗試：2026-05-01 來源：Day 16 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

1. Explain why LC 743 needs Dijkstra instead of BFS.

當天筆記摘錄
#

Problem 3 - LC 743 Network Delay Time Review
#

Status: Good enough no-hints recall.
Pattern: Dijkstra / single-source shortest path.

Why Dijkstra Fits
#

We need:

minimum travel time from one source node k to every other node

The graph is:

directed
weighted
non-negative edge costs

That is the standard Dijkstra fit.

Core Data Structures
#

adjacency list
min-heap of (time, node)
either:
- shortest-distance table, or
- finalized / visited set

Final Answer Meaning
#

This is not:

the longest arbitrary path from source

It is:

the maximum shortest-path arrival time from source to any reachable node

So:

if some node is unreachable -> return -1
else -> return the maximum shortest arrival time

Complexity
#

Time: O((E + V) log V)
Space: O(E + V)

Common Mistakes
#

using BFS even though edge weights differ
saying the answer is the “longest path”
forgetting to skip stale heap entries or revisits

Interview-Ready Explanation
#

I run Dijkstra from node k to compute the shortest signal arrival time to every node. If I cannot reach all nodes, I return -1. Otherwise I return the largest shortest arrival time, because that is when the last node receives the signal.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from collections import defaultdict
from heapq import heappop, heappush
from typing import List

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        dist = {}
        heap = [(0, k)]
        while heap:
            d, node = heappop(heap)
            if node in dist:
                continue
            dist[node] = d
            for nei, w in graph[node]:
                if nei not in dist:
                    heappush(heap, (d + w, nei))

        return max(dist.values()) if len(dist) == n else -1