WITH EXPLAINATION POSSIBLE 2 SOLUTIONS IN c++
1.bellman Ford solution\n\n  // Solution1: Bellman Ford or dfs\n    // TC: O(nE), E = no. of edges\n    // SC: O(n)\n    int bellmanFord(vector<vector<int>>& ti
1.bellman Ford solution\n```\n  // Solution1: Bellman Ford or dfs\n    // TC: O(nE), E = no. of edges\n    // SC: O(n)\n    int bellmanFord(vector<vector<int>>& times, int n, int k) {\n        // delay[i] = time to reach kth node\n        vector<int> delay(n+1, INT_MAX);\n        // we start from  node kth node as source, all other nodes are destinations\n        delay[k] = 0;\n        \n        for(int i = 0; i < n; i++) {\n            for(auto edge: times) {\n                // delay[dst] > delay[src] + wt\n                delay[edge[1]] = min(delay[edge[1]], \n                                     delay[edge[0]] == INT_MAX ? INT_MAX : delay[edge[0]] + edge[2]);\n            }\n        }\n        // 0th element is dummy, so skip . Find the max delay time, this will decide the overall delay\n        int max_delay = *max_element(delay.begin() + 1, delay.end());\n        \n        return max_delay == INT_MAX ? -1 : max_delay;\n    }\n\t   int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n        return bellmanFord(times, n, k);\n    }\n```\nOPTIMISE SOLUTION\n\n2.djikstra solution\n```\nint djikstra(vector<vector<int>>& times, int n, int k) {\n        // create graph, 0th node is dummy\n        // node: <dst, time>\n        vector<vector<pair<int, int> > > g(n+1);\n            \n        for(auto edge: times) \n            g[edge[0]].emplace_back(make_pair(edge[1], edge[2]));\n        \n        // delay[i] = min time to reach kth node\n        vector<int> delay(n+1, INT_MAX);\n        \n        auto comp = [&](const array<int, 2>& a, const array<int, 2>& b) { return a[1] >= b[1]; };    \n        // <node, time>\n        priority_queue<array<int, 2>, vector<array<int, 2>>, decltype(comp)> min_heap(comp);\n        min_heap.push({k, 0});\n        // starting dist will be 0\n        delay[k] = 0;\n        \n        while(!min_heap.empty()) {\n            auto [curr, curr_time] = min_heap.top();\n            min_heap.pop();\n            \n            if(delay[curr] > curr_time)\n                continue;\n            \n            for(auto [dst, t]: g[curr]) {\n                if(delay[dst] > delay[curr] + t) {\n                    delay[dst] = delay[curr] + t;\n                    min_heap.push({dst, delay[curr] + t});\n                }\n            }\n        }\n        \n        int max_delay = *max_element(delay.begin() + 1, delay.end());\n        return max_delay == INT_MAX ? -1 : max_delay;\n    }\n    \n    int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n        return djikstra(times, n, k);\n    }\n};\n// TC: O(ElogE) + O(V+E)\n```
['Depth-First Search', 'C']