Network Delay Time

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

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;

public class NetworkDelayTime {
    public static void main(String[] args) {
        int times[][] = { { 2, 1, 1 }, { 2, 3, 1 }, { 3, 4, 1 } };
        int n = 4, k = 2;
        System.out.println(networkDelayTime(times, n, k));
    }

    // visited list
    static public int visited[];

    // dfs function
    static void dfs(int id, int sum) {
        if (sum < visited[id])
            visited[id] = sum;
        else
            return;
        for (int[] p : adj.get(id))
            dfs(p[0], sum + p[1]);

    }

    static ArrayList<ArrayList<int[]>> adj;

    static int networkDelayTime(int[][] times, int N, int K) {
        adj = new ArrayList<>();
        visited = new int[N + 1];
        Arrays.fill(visited, Integer.MAX_VALUE);
        for (int i = 1; i <= N + 1; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] v : times) {
            adj.get(v[0]).add(new int[] { v[1], v[2] });
        }

        dfs(K, 0);

        int res = 0;
        for (int i = 1; i <= N; i++) {
            if (visited[i] == Integer.MAX_VALUE)
                return -1;
            res = Math.max(visited[i], res);
        }
        return res;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;


vector<int> visits;
vector<vector<pair<int, int>>> edgeMap;

//dfs funtion
void dfs(int id, int sum)
{
        if(sum < visits[id]) 
             visits[id] = sum;
        else
           return;
        
        for(pair<int, int> p : edgeMap[id])
                 dfs(p.first, sum + p.second);
}

int networkDelayTime(vector<vector<int>>& times, int N, int K)
{
        visits.resize(N+1, INT_MAX);
        edgeMap.resize(N+1);
        for(vector<int> v : times) 
            edgeMap[v[0]].push_back(make_pair(v[1], v[2]));
        
        dfs(K, 0);
        
        int res = 0;
        for(int i=1;i<=N;i++)
        {
            if(visits[i] == INT_MAX) 
                  return -1;
            res = max(visits[i], res);
        }
        return res; 
}
int main()
{
   vector<vector<int>> times = {{2,1,1},{2,3,1},{3,4,1}};
   int n = 4, k = 2;
   cout<<networkDelayTime(times,n,k);
   return 0;
}