import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    dist = {i: float('inf') for i in range(1, n + 1)}
    dist[k] = 0

    pq = [(0, k)]

    while pq:
        time, node = heapq.heappop(pq)

        if time > dist[node]:
            continue

        for neighbour, neighbourTime in graph[node]:
            candidate_dist = time + neighbourTime
            if candidate_dist < dist[neighbour]:
                dist[neighbour] = candidate_dist
                heapq.heappush(pq, (candidate_dist, neighbour))

    maxTime = max(dist.values())
    return maxTime if maxTime < float('inf') else -1

The algorithm uses Dijkstra's shortest path algorithm to find the shortest time it takes for the signal to reach every node.

1. Create an adjacency list (graph) to represent the times between nodes. (note: we use different data structures depending on the language, but the idea is the same)
2. Initialize a distance array (dist) to store the shortest time it takes for the signal to arrive at each node. Set the initial values to infinity (maximum possible time) except for node k, which is set to 0 as it's the source.
3. Create a priority queue (pq) to store the time it takes to visit a node. Initialize it with node k and time 0.
4. Iterate through the priority queue while it's not empty: a. Pop the node with the smallest time from the priority queue. b. Check if the current time is greater than the distance for the current node; if true, continue to the next iteration. c. For each neighbor's node in the graph, compare the sum of the current time and travel time to reach the neighbor with the minimum distance for the neighbor in the dist array. If the new calculated time is less, update the dist array and push the neighbor with the new calculated time into the priority queue.
5. After the loop is finished, find the maximum value in the dist array (ignoring the first value, which is a placeholder). If the maximum value is infinity, return -1, as not all nodes could receive the signal. Otherwise, return the maximum time.

#include <vector>
#include <queue>
#include <algorithm>
#include <limits>

int networkDelayTime(std::vector<std::vector<int>>& times, int n, int k) {
    std::vector<std::vector<std::pair<int, int>>> graph(n + 1);
    for (const auto &edge : times)
        graph[edge[0]].emplace_back(edge[1], edge[2]);

    std::vector<int> dist(n + 1, std::numeric_limits<int>::max());
    dist[k] = 0;

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.emplace(0, k);

    while (!pq.empty()) {
        int time = pq.top().first, node = pq.top().second;
        pq.pop();

        if (time > dist[node]) continue;
        for (const auto &neighbour : graph[node]) {
            int nextNode = neighbour.first, nextTime = neighbour.second;
            if (time + nextTime < dist[nextNode]) {
                dist[nextNode] = time + nextTime;
                pq.push({dist[nextNode], nextNode});
            }
        }
    }

    int maxTime = *std::max_element(dist.begin() + 1, dist.end());
    return maxTime == std::numeric_limits<int>::max() ? -1 : maxTime;
}

The algorithm uses Dijkstra's shortest path algorithm to find the shortest time it takes for the signal to reach every node.

1. Create an adjacency list (graph) to represent the times between nodes. (note: we use different data structures depending on the language, but the idea is the same)
2. Initialize a distance array (dist) to store the shortest time it takes for the signal to arrive at each node. Set the initial values to infinity (maximum possible time) except for node k, which is set to 0 as it's the source.
3. Create a priority queue (pq) to store the time it takes to visit a node. Initialize it with node k and time 0.
4. Iterate through the priority queue while it's not empty: a. Pop the node with the smallest time from the priority queue. b. Check if the current time is greater than the distance for the current node; if true, continue to the next iteration. c. For each neighbor's node in the graph, compare the sum of the current time and travel time to reach the neighbor with the minimum distance for the neighbor in the dist array. If the new calculated time is less, update the dist array and push the neighbor with the new calculated time into the priority queue.
5. After the loop is finished, find the maximum value in the dist array (ignoring the first value, which is a placeholder). If the maximum value is infinity, return -1, as not all nodes could receive the signal. Otherwise, return the maximum time.