Problem Statement

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

Problem Link

Network Delay Time - LeetCode

Reference Link

https://www.youtube.com/watch?v=YHx6r9pM5e0&list=PLEJXowNB4kPzByLnnFYNSCoqtFz0VKLk5&index=31&ab_channel=TECHDOSE

Code (Dijkstra Algorithm)

#define pp pair<int,int>
class Solution {
public:
    // The idea here is find the shortest path from k to the farthest vertex
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        
        vector<int> weight(n+1,1e9); // will store the shortest distance of all nodes from source k
        weight[k] = 0;
        vector<pp> adj[n+1];
        
        for(auto time:times)
        {
            int src = time[0];
            int dst = time[1];
            int wt = time[2];
            
            adj[src].push_back({dst,wt});
            
        }
        
        priority_queue<pp,vector<pp>,greater<pp>> pq;
        
        pq.push({0,k});
        
        while(!pq.empty())
        {
            auto p = pq.top();
            int u = p.second;
            int wt = p.first;
            pq.pop();
            
            for(pp v:adj[u])
            {
                
               
               if(weight[v.first] > wt+v.second)
                {
                    weight[v.first] = wt+v.second;
                    pq.push({weight[v.first],v.first});
                  
                   
                }
            }
          
             
        }
        
        // Shortest path from k to the farthest vertex   
        int maxdist =  *max_element(weight.begin()+1,weight.end());
        
        return maxdist==1e9?-1:maxdist;
        
    }
};