743. Network Delay Time
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
Дана сеть из узлов, помеченных от 1 до n. Также given times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. return минимальное время, которое поit is required всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, return -1.
Ví dụ:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
C# lời giải
đã khớp/gốcusing 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++ lời giải
bản nháp tự động, xem lại trước khi gửi#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 lời giải
đã khớp/gốcimport 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 lời giải
đã khớp/gốcvar 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 lời giải
đã khớp/gốcimport 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 -1Go lời giải
đã khớp/gốcpackage 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
Представьте đồ thị в виде списка смежности.
Используйте Dijkstra's algorithm для нахождения кратчайших путей от узла k до всех других узлов.
find максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, return -1.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.
Chưa có việc làm đang hoạt động.