> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/07-19-2022-743.-network-delay-time.md).

# 07/19/2022 743. Network Delay Time

Method: use Dijkastral's algorithm. First build adjacency list using hashmap which key is the source vertex and value is the pair with dest vertex and time. Create a int array minDis with the size of n + 1, initialize them all with infinity value. Create a min Heap containing Pair and sorted by the pair's value. We add the pair of k and 0 to the pq. While pq is not empty, we remove one from the pq, set currNode with the key and currTime with the value. If currTime is greater than the minDis\[currNode], we omit. if the adjacency list doesn't contain this currNode, we omit. Then for all neighbour of the currNode, we get the weight and neighbour node, if the minDis\[neighbour] > currWeight + weight, we update the minDist\[neighbour]. Finally, we iterate the minDis from 1 to n+1, if the max value is infinity, we return -1, otherwise, we return the max value.

Time O(V + ELOGV)

Space O(V + E)

```
// Some code
adj.putIfAbsent(source, new ArrayList<>());
adj.get(source).add(new Pair(travelTime, dest));

```

```
// Some code
List<Pair<Integer, Integer>> list = adjacency_list.getOrDefault(source, new ArrayList());
list.add(new Pair(dest, weight));
adjacency_list.put(source, list);
```