어려움그래프다익스트라힙

그래프 + 최적화

정점 개수 n, 방향 가중 간선 목록 edges, 시작 정점 source가 주어져요. 각 원소 [u, v, w]는 u에서 v로 신호가 가는 데 w만큼 걸린다는 뜻이에요.

source에서 신호를 보냈을 때 모든 정점에 신호가 닿는 데 걸리는 시간을 반환해요. 이는 source에서 각 정점까지의 최단 시간 중 가장 큰 값이에요. 한 정점이라도 신호를 받지 못하면 -1을 반환해요.

한 정점에서 전체로 가는 최단 거리는 다익스트라예요. 거기서 최댓값을 취하고, 무한대(못 닿음)가 하나라도 있으면 -1로 처리하면 돼요.

JavaScript는 스타터의 MinHeap을, 파이썬은 heapq를 써요.

예시

예시 1

입력: n = 4, edges = [[0, 1, 1], [0, 2, 4], [1, 2, 1], [2, 3, 1]], source = 0
출력: 3
설명: 0→1(1), 0→1→2(2), 0→1→2→3(3)이라 가장 오래 걸리는 곳이 3이에요.

예시 2

입력: n = 3, edges = [[0, 1, 2]], source = 0
출력: -1
설명: 2번 정점은 신호를 받지 못해요.

제한 사항

1 ≤ n ≤ 100,000
0 ≤ edges.length ≤ 300,000
0 ≤ u, v, source < n, 0 ≤ w ≤ 10,000

다익스트라로 source에서 모든 정점까지의 최단 거리를 구해요. 거리 배열을 훑어 무한대가 하나라도 있으면 -1을, 아니면 가장 큰 거리를 반환해요.

javascript
Copy code
class MinHeap {
  /** @param {(a: any, b: any) => number} [compare] 음수면 a가 먼저 나옵니다. */
  constructor(compare) {
    this.items = [];
    this.compare = compare ?? ((a, b) => (a < b ? -1 : a > b ? 1 : 0));
  }
  get size() {
    return this.items.length;
  }
  peek() {
    return this.items.length > 0 ? this.items[0] : null;
  }
  push(value) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(a[parent], a[i]) <= 0) break;
      [a[parent], a[i]] = [a[i], a[parent]];
      i = parent;
    }
  }
  pop() {
    const a = this.items;
    if (a.length === 0) return null;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = i * 2 + 1;
        const r = l + 1;
        let small = i;
        if (l < a.length && this.compare(a[l], a[small]) < 0) small = l;
        if (r < a.length && this.compare(a[r], a[small]) < 0) small = r;
        if (small === i) break;
        [a[small], a[i]] = [a[i], a[small]];
        i = small;
      }
    }
    return top;
  }
}
function networkDelay(n, edges, source) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) graph[u].push([v, w]);
  const dist = new Array(n).fill(Infinity);
  dist[source] = 0;
  const heap = new MinHeap((a, b) => a[0] - b[0]);
  heap.push([0, source]);
  while (heap.size > 0) {
    const [d, v] = heap.pop();
    if (d > dist[v]) continue;
    for (const [next, w] of graph[v]) {
      if (dist[v] + w < dist[next]) {
        dist[next] = dist[v] + w;
        heap.push([dist[next], next]);
      }
    }
  }
  let ans = 0;
  for (const d of dist) {
    if (d === Infinity) return -1;
    ans = Math.max(ans, d);
  }
  return ans;
}

이전 문제DP 또는 그리디 판단

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.