Best O(ElogV) Solution
Approach\nDijkstra\'s Algorithm\n\n# Complexity\n- Time complexity:\nO(ElogV)\n\n- Space complexity:\nO(V + E)\n\n# Code\n\nclass Solution {\npublic:\n    int n
# Approach\nDijkstra\'s Algorithm\n\n# Complexity\n- Time complexity:\n$$O(ElogV)$$\n\n- Space complexity:\n$$O(V + E)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n        vector <pair<int, int>> adj[n+1];\n        for (auto it: times) \n            adj[it[0]].push_back({it[1], it[2]});\n        priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;\n        pq.push({0, k});\n        vector <int> time(n+1, 1e9);\n        time[k] = 0;\n        while (!pq.empty()) {\n            int t = pq.top().first;\n            int node = pq.top().second;\n            pq.pop();\n            for (auto it: adj[node]) {\n                int adjNode = it.first;\n                int wt = it.second;\n                if (t + wt < time[adjNode]) {\n                    time[adjNode] = t + wt;\n                    pq.push({t + wt, adjNode});\n                }\n            }\n        }\n        int minTime = INT_MIN;\n        for (int i = 1; i <= n; i++) {\n            if (time[i] == 1e9)\n                return -1;\n            minTime = max (time[i], minTime);    \n        }\n        return minTime;\n    }\n};\n```
['C++']