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.)
- code wrong
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
distance = [inf] * (n + 1)
distance[0] = 0
distance[k] = 0
graph = defaultdict(list) # nei, distance
for i, j, w in times:
graph[i].append((j, w))
q = deque([k])
visited = set()
while q:
cur = q.popleft()
visited.add(cur)
for nei, w in graph[cur]:
distance[nei] = min(distance[nei], distance[cur] + w)
if nei not in visited:
q.append(nei)
print(distance)
ans = max(distance)
return ans if ans != inf else -1
After starting point A, for neighbour B,C,D, can only choose B or C in the next round as they are the shortest, can’t choose D.
- code #dijkstra
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
distance = [inf] * (n + 1)
distance[0] = 0 # reduntant
graph = defaultdict(list) # nei, distance
for i, j, w in times:
graph[i].append((j, w))
q = [[0, k]] # distance, point
while q:
cur_dis, cur = heapq.heappop(q)
if distance[cur] != inf: continue
distance[cur] = cur_dis
for nei, w in graph[cur]:
if distance[nei] == inf:
heapq.heappush(q, (cur_dis + w, nei))
ans = max(distance)
return ans if ans != inf else -1
- code
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int[] time: times){
// List<int[]> nei_wei = graph.getOrDefault(time[0], new ArrayList<int[]>());
// nei_wei.add(new int[] {time[1], time[2]});
// graph.put(time[0], nei_wei);
if (!graph.containsKey(time[0]))
graph.put(time[0], new ArrayList<int[]>());
graph.get(time[0]).add(new int[]{time[1], time[2]});
}
Map<Integer, Integer> dist = new HashMap<>();
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0] - b[0]);
pq.offer(new int[] {0, k});
while (!pq.isEmpty()){
int[] cur_dis_node = pq.poll();
int curDis = cur_dis_node[0];
int cur = cur_dis_node[1];
if (dist.containsKey(cur)) continue;
dist.put(cur, curDis);
if (graph.containsKey(cur)){
for (int[] nei_w: graph.get(cur)){
int nei = nei_w[0], w = nei_w[1];
if(!dist.containsKey(nei)){
pq.offer(new int[]{curDis + w, nei});
}
}
}
}
if(dist.size() != n) return -1;
return dist.values().stream().max(Comparator.naturalOrder()).get();
// int res = 0;
// for (int v: dist.values()){
// res = Math.max(v, res);
// }
// return res;
}
}