743. Network Delay Time

leetcode medium

#array#csharp#graph#hash-table#heap#leetcode#math#medium#sort

Task

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

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

Output: 2

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        var graph = new Dictionary<int, List<int[]>>();
        for (int i = 1; i <= n; i++) {
            graph[i] = new List<int[]>();
        }
        foreach (var time in times) {
            graph[time[0]].Add(new int[]{time[1], time[2]});
        }
        var minHeap = new SortedSet<(int time, int node)>(Comparer<(int, int)>.Create((a, b) => a.time != b.time ? a.time - b.time : a.node - b.node));
        minHeap.Add((0, k));
        var minTime = new Dictionary<int, int>();
        for (int i = 1; i <= n; i++) {
            minTime[i] = int.MaxValue;
        }
        minTime[k] = 0;
        while (minHeap.Count > 0) {
            var (time, node) = minHeap.Min;
            minHeap.Remove(minHeap.Min);
            foreach (var neighbor in graph[node]) {
                int newTime = time + neighbor[1];
                if (newTime < minTime[neighbor[0]]) {
                    minHeap.Remove((minTime[neighbor[0]], neighbor[0]));
                    minTime[neighbor[0]] = newTime;
                    minHeap.Add((newTime, neighbor[0]));
                }
            }
        }
        int maxTime = int.MinValue;
        foreach (var t in minTime.Values) {
            if (t == int.MaxValue) return -1;
            maxTime = Math.Max(maxTime, t);
        }
        return maxTime;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NetworkDelayTime(int[][] times, int n, int k) {
        var graph = new unordered_map<int, List<int[]>>();
        for (int i = 1; i <= n; i++) {
            graph[i] = new List<int[]>();
        }
        foreach (var time in times) {
            graph[time[0]].push_back(new int[]{time[1], time[2]});
        }
        var minHeap = new SortedSet<(int time, int node)>(Comparer<(int, int)>.Create((a, b) => a.time != b.time ? a.time - b.time : a.node - b.node));
        minHeap.push_back((0, k));
        var minTime = new unordered_map<int, int>();
        for (int i = 1; i <= n; i++) {
            minTime[i] = int.MaxValue;
        }
        minTime[k] = 0;
        while (minHeap.size() > 0) {
            var (time, node) = minHeap.Min;
            minHeap.Remove(minHeap.Min);
            foreach (var neighbor in graph[node]) {
                int newTime = time + neighbor[1];
                if (newTime < minTime[neighbor[0]]) {
                    minHeap.Remove((minTime[neighbor[0]], neighbor[0]));
                    minTime[neighbor[0]] = newTime;
                    minHeap.push_back((newTime, neighbor[0]));
                }
            }
        }
        int maxTime = int.MinValue;
        foreach (var t in minTime.Values) {
            if (t == int.MaxValue) return -1;
            maxTime = max(maxTime, t);
        }
        return maxTime;
    }
}

Java solution

matched/original

import java.util.*;

public class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] time : times) {
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        }

        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        minHeap.add(new int[]{0, k});
        Map<Integer, Integer> minTime = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            minTime.put(i, Integer.MAX_VALUE);
        }
        minTime.put(k, 0);

        while (!minHeap.isEmpty()) {
            int[] top = minHeap.poll();
            int time = top[0];
            int node = top[1];
            for (int[] neighbor : graph.get(node)) {
                int newTime = time + neighbor[1];
                if (newTime < minTime.get(neighbor[0])) {
                    minTime.put(neighbor[0], newTime);
                    minHeap.add(new int[]{newTime, neighbor[0]});
                }
            }
        }

        int maxTime = Collections.max(minTime.values());
        return maxTime == Integer.MAX_VALUE ? -1 : maxTime;
    }
}

JavaScript solution

matched/original

var networkDelayTime = function(times, n, k) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [u, v, w] of times) {
        graph[u].push([v, w]);
    }

    const minHeap = [[0, k]];
    const minTime = Array(n + 1).fill(Infinity);
    minTime[k] = 0;

    while (minHeap.length) {
        minHeap.sort((a, b) => a[0] - b[0]);
        const [time, node] = minHeap.shift();
        for (const [neighbor, t] of graph[node]) {
            const newTime = time + t;
            if (newTime < minTime[neighbor]) {
                minTime[neighbor] = newTime;
                minHeap.push([newTime, neighbor]);
            }
        }
    }

    const maxTime = Math.max(...minTime.slice(1));
    return maxTime === Infinity ? -1 : maxTime;
};

Python solution

matched/original

import heapq

def networkDelayTime(times, n, k):
    graph = {i: [] for i in range(1, n + 1)}
    for u, v, w in times:
        graph[u].append((v, w))

    min_heap = [(0, k)]
    min_time = {i: float('inf') for i in range(1, n + 1)}
    min_time[k] = 0

    while min_heap:
        time, node = heapq.heappop(min_heap)
        for neighbor, t in graph[node]:
            new_time = time + t
            if new_time < min_time[neighbor]:
                min_time[neighbor] = new_time
                heapq.heappush(min_heap, (new_time, neighbor))

    max_time = max(min_time.values())
    return max_time if max_time < float('inf') else -1

Go solution

matched/original

package main

import (
  "container/heap"
  "math"
)

type Edge struct {
  to, weight int
}

type MinHeap [][]int

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i][0] < h[j][0] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.([]int)) }
func (h *MinHeap) Pop() interface{} {
  old := *h
  n := len(old)
  x := old[n-1]
  *h = old[0 : n-1]
  return x
}

func networkDelayTime(times [][]int, n int, k int) int {
  graph := make(map[int][]Edge)
  for _, time := range times {
    graph[time[0]] = append(graph[time[0]], Edge{time[1], time[2]})
  }

  minHeap := &MinHeap{}
  heap.Init(minHeap)
  heap.Push(minHeap, []int{0, k})
  minTime := make(map[int]int)
  for i := 1; i <= n; i++ {
    minTime[i] = math.MaxInt32
  }
  minTime[k] = 0

  for minHeap.Len() > 0 {
    t := heap.Pop(minHeap).([]int)
    time, node := t[0], t[1]
    for _, edge := range graph[node] {
      newTime := time + edge.weight
      if newTime < minTime[edge.to] {
        minTime[edge.to] = newTime
        heap.Push(minHeap, []int{newTime, edge.to})
      }
    }
  }

  maxTime := 0
  for _, t := range minTime {
    if t == math.MaxInt32 {
      return -1
    }
    if t > maxTime {
      maxTime = t
    }
  }
  return maxTime
}

Explanation

Algorithm

Представьте граф в виде списка смежности.

Используйте алгоритм Дейкстры для нахождения кратчайших путей от узла k до всех других узлов.

Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1.

😎