Formatted question description: https://leetcode.ca/all/743.html

743. Network Delay Time (Medium)

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2


Note:

1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

Related Topics:
Heap, Depth-first Search, Breadth-first Search, Graph

Solution 1. Dijkstra

// OJ: https://leetcode.com/problems/network-delay-time/
// Time: O(E + VlogV)
// Space: O(E)
class Solution {
typedef unordered_map<int, unordered_map<int, int>> Graph;
typedef pair<int, int> iPair;
vector<int> dijkstra(Graph graph, int N, int source) {
priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
vector<int> dists(N, INT_MAX);
pq.emplace(0, source);
dists[source] = 0;
while (pq.size()) {
int u = pq.top().second;
pq.pop();
for (auto neighbor : graph[u]) {
int v = neighbor.first, weight = neighbor.second;
if (dists[v] > dists[u] + weight) {
dists[v] = dists[u] + weight;
pq.emplace(dists[v], v);
}
}
}
return dists;
}
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
Graph graph;
for (auto e : times) graph[e[0] - 1][e[1] - 1] = e[2];
auto dists = dijkstra(graph, N, K - 1);
int ans = 0;
for (int d : dists) {
if (d == INT_MAX) return -1;
ans = max(ans, d);
}
return ans;
}
};


Solution 2. Bellman-Ford

// OJ: https://leetcode.com/problems/network-delay-time/
// Time: O(VE)
// Space: O(V)
class Solution {
vector<int> bellmanFord(vector<vector<int>>& edges, int V, int src) {
vector<int> dist(V, INT_MAX);
dist[src - 1] = 0;
for (int i = 1; i < V; ++i) {
for (auto &e : edges) {
int u = e[0] - 1, v = e[1] - 1, w = e[2];
if (dist[u] == INT_MAX) continue;
dist[v] = min(dist[v], dist[u] + w);
}
}
return dist;
}
public:
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
auto dist = bellmanFord(times, N, K);
int ans = *max_element(dist.begin(), dist.end());
return ans == INT_MAX ? -1 : ans;
}
};

• class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
Map<Integer, List<int[]>> travelMap = new HashMap<Integer, List<int[]>>();
for (int[] time : times) {
int source = time[0] - 1, target = time[1] - 1, lapse = time[2];
List<int[]> travels = travelMap.getOrDefault(source, new ArrayList<int[]>());
travelMap.put(source, travels);
}
for (int i = 0; i < N; i++)
queue.offer(new int[]{K - 1, 0});
while (!queue.isEmpty()) {
int[] nodeTime = queue.poll();
int node = nodeTime[0], time = nodeTime[1];
List<int[]> travels = travelMap.getOrDefault(node, new ArrayList<int[]>());
for (int[] travel : travels) {
int target = travel[0], lapse = travel[1];
int totalLapse = time + lapse;
queue.offer(new int[]{target, totalLapse});
}
}
}
int maxTime = 0;
for (int time : received) {
if (time == Integer.MAX_VALUE)
return -1;
else
maxTime = Math.max(maxTime, time);
}
return maxTime;
}
}

############

class Solution {
private static final int N = 110;
private static final int INF = 0x3f3f;

public int networkDelayTime(int[][] times, int n, int k) {
int[][] g = new int[N][N];
for (int i = 0; i < N; ++i) {
Arrays.fill(g[i], INF);
}
for (int[] e : times) {
g[e[0]][e[1]] = e[2];
}
int[] dist = new int[N];
Arrays.fill(dist, INF);
dist[k] = 0;
boolean[] vis = new boolean[N];
for (int i = 0; i < n; ++i) {
int t = -1;
for (int j = 1; j <= n; ++j) {
if (!vis[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
vis[t] = true;
for (int j = 1; j <= n; ++j) {
dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans = Math.max(ans, dist[i]);
}
return ans == INF ? -1 : ans;
}
}

• // OJ: https://leetcode.com/problems/network-delay-time/
// Time: O(E + VlogV)
// Space: O(E)
class Solution {
typedef pair<int, int> PII;
public:
int networkDelayTime(vector<vector<int>>& E, int n, int k) {
vector<vector<PII>> G(n);
for (auto &e : E) G[e[0] - 1].emplace_back(e[1] - 1, e[2]);
vector<int> dist(n, INT_MAX);
dist[k - 1] = 0;
priority_queue<PII, vector<PII>, greater<>> pq;
pq.emplace(0, k - 1);
while (pq.size()) {
auto [cost, u] = pq.top();
pq.pop();
if (dist[u] > cost) continue;
for (auto &[v, w] : G[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.emplace(dist[v], v);
}
}
}
int ans = *max_element(begin(dist), end(dist));
return ans == INT_MAX ? -1 : ans;
}
};

• class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
INF = 0x3F3F
g = defaultdict(list)
for u, v, w in times:
g[u - 1].append((v - 1, w))
dist = [INF] * n
dist[k - 1] = 0
q = [(0, k - 1)]
while q:
_, u = heappop(q)
for v, w in g[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heappush(q, (dist[v], v))
ans = max(dist)
return -1 if ans == INF else ans

############

class Solution:
def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
K -= 1
nodes = collections.defaultdict(list)
for u, v, w in times:
nodes[u - 1].append((v - 1, w))
dist = [float('inf')] * N
dist[K] = 0
done = set()
for _ in range(N):
smallest = min((d, i) for (i, d) in enumerate(dist) if i not in done)[1]
for v, w in nodes[smallest]:
if v not in done and dist[smallest] + w < dist[v]:
dist[v] = dist[smallest] + w
return -1 if float('inf') in dist else max(dist)

• const Inf = 0x3f3f3f3f

type pair struct {
first  int
second int
}

var _ heap.Interface = (*pairs)(nil)

type pairs []pair

func (a pairs) Len() int { return len(a) }
func (a pairs) Less(i int, j int) bool {
return a[i].first < a[j].first || a[i].first == a[j].first && a[i].second < a[j].second
}
func (a pairs) Swap(i int, j int)   { a[i], a[j] = a[j], a[i] }
func (a *pairs) Push(x interface{}) { *a = append(*a, x.(pair)) }
func (a *pairs) Pop() interface{}   { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }

func networkDelayTime(times [][]int, n int, k int) int {
graph := make([]pairs, n)
for _, time := range times {
from, to, time := time[0]-1, time[1]-1, time[2]
graph[from] = append(graph[from], pair{to, time})
}

dis := make([]int, n)
for i := range dis {
dis[i] = Inf
}
dis[k-1] = 0

vis := make([]bool, n)
h := make(pairs, 0)
heap.Push(&h, pair{0, k - 1})
for len(h) > 0 {
from := heap.Pop(&h).(pair).second
if vis[from] {
continue
}
vis[from] = true
for _, e := range graph[from] {
to, d := e.first, dis[from]+e.second
if d < dis[to] {
dis[to] = d
heap.Push(&h, pair{d, to})
}
}
}

ans := math.MinInt32
for _, d := range dis {
ans = max(ans, d)
}
if ans == Inf {
return -1
}
return ans
}

func max(x, y int) int {
if x > y {
return x
}
return y
}