743. Network Delay Time

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;
    }
}

#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;
    }
}

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;
    }
}

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;
};

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

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
}

Algorithm

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

Используйте Dijkstra's algorithm для нахождения кратчайших путей от узла k до всех других узлов.

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

😎