Portfolio

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 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.

Example 1:


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

Example 2:


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

Example 3:


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

Constraints:

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.)

풀이

은찬


const networkDelayTime = (times, n, k) => {
    let answer = 0;
    const graph = Array.from({length: n + 1}, () => Array());
    const dist = Array(n + 1).fill(Infinity);
    const queue = [];
    
    for(let i = 0; i < times.length; i++){
        const [start, end, cost] = times[i];
        
        graph[start].push([end, cost]);
    }
    
    queue.push([k, 0]);
    dist[k] = 0;
    
    while(queue.length){
        const [current, cost] = queue.shift();
        
        for(let i = 0; i < graph[current].length; i++){
            const [next, nextCost] = graph[current][i];
            
            if(dist[next] > dist[current] + nextCost){
                dist[next] = dist[current] + nextCost;
                queue.push([next, nextCost]);
            }
        }
    }
    
    for(let i = 1; i <= n; i++){
        if(dist[i] === Infinity){
            return -1;
        }
        answer = answer < dist[i] ? dist[i] : answer;
    }
    
    return answer;
};

재영


class MinHeap {
  constructor() {
    this.heap = [null];
  }

  heappush(val) {
    this.heap.push(val);
    let nowIndex = this.heap.length - 1;
    let parentIndex = this.getParentIndex(nowIndex);

    while (nowIndex > 1 && this.heap[nowIndex][1] < this.heap[parentIndex][1]) {
      this.swap(nowIndex, parentIndex);
      nowIndex = parentIndex;
      parentIndex = this.getParentIndex(nowIndex);
    }
  }

  heappop() {
    if (this.heap.length === 1) return;
    if (this.heap.length === 2) return this.heap.pop();

    const min = this.heap[1];
    this.heap[1] = this.heap.pop();

    let [nowIndex, leftIndex, rightIndex] = this.getUpdatedindices(1);

    if (leftIndex > this.heap.length - 1) {
      return min;
    }
    if (
      rightIndex > this.heap.length - 1 &&
      this.heap[leftIndex][1] < this.heap[nowIndex][1]
    ) {
      this.swap(nowIndex, leftIndex);
      return min;
    }
    while (
      leftIndex < this.heap.length - 1 &&
      rightIndex < this.heap.length &&
      (this.heap[leftIndex][1] < this.heap[nowIndex][1] ||
        this.heap[nowIndex][1] < this.heap[leftIndex][1])
    ) {
      const minIndex =
        this.heap[rightIndex][1] < this.heap[leftIndex][1]
          ? leftIndex
          : rightIndex;
      this.swap(minIndex, nowIndex);
      [nowIndex, leftIndex, rightIndex] = this.getUpdatedindices(minIndex);
    }

    return min;
  }

  getParentIndex(index) {
    return Math.floor(index / 2);
  }

  getUpdatedindices(index) {
    return [index, index * 2, index * 2 + 1];
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
}
const networkDelayTime = (times, n, k) => {
  const minHeap = new MinHeap();

  const graph = {};
  const distance = new Array(n).fill(Infinity);

  times.forEach(([from, to, cost]) => {
    if (graph[from] === undefined) graph[from] = [];
    if (graph[to] === undefined) graph[to] = [];
    graph[from].push([to, parseInt(cost)]);
  });
  const start = k;
  distance[start - 1] = 0;

  minHeap.heappush([0, start]);

  while (minHeap.heap.length > 1) {
    const [dist, now] = minHeap.heappop();
    for (const [to, cost] of graph[now]) {
      let nextDist = dist + cost;
      if (nextDist < distance[to - 1]) {
        distance[to - 1] = nextDist;
        minHeap.heappush([nextDist, to]);
      }
    }
  }
  const result = Math.max(...distance);
  return result !== Infinity ? result : -1;
};

효성


var networkDelayTime = function(times, n, k) {
    const board = Array(n+1).fill(Infinity);
    board[k] = 0;
    
    for(let i=0; i<n; i++) {
        for(const [u, v, w] of times) {
            if(board[u] === Infinity) continue;
            if(board[v] > board[u] + w) {
                board[v] = board[u] + w;
            }
        }
    }
    let answer = 0;
    for(let i=1; i<=n; i++) {
        answer = Math.max(answer, board[i]);
    }
    return answer === Infinity ? -1 : answer;
};

Network Delay Time

풀이