C++ | Dijkstra's Algorithm
\nclass Solution {\n\tpublic:\n\t\t  int networkDelayTime(vector<vector<int>>& times, int N, int K) {\t\n\t\t  // smallest element will be on top (as we require
```\nclass Solution {\n\tpublic:\n\t\t  int networkDelayTime(vector<vector<int>>& times, int N, int K) {\t\n\t\t  // smallest element will be on top (as we require to choose next smallest distace node to select)\n\t\t  // Node (u,v,w) : u=>v with weight as w\n\t\t  // pq(min_distace of vertex v, v)\n\t\t  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;\n\t\t  // as node range from (1,N)\n\t\t  // initialize all distance as infinity excluding starting vertex \n\t\t  vector<int>dist(N+1, INT_MAX);\n\t\t  // as we are starting from vertex K so its distance is considered as 0\n\t\t  pq.push(make_pair(0, K));\n\t\t  dist[K] = 0;\n\n\t\t  // Creating adjacency list from given times \n\t\t  unordered_map<int, vector<pair<int, int>>>adj;\n\t\t  for (int i = 0; i < times.size(); i++)\n\t\t\t adj[times[i][0]].push_back(make_pair(times[i][1], times[i][2]));\n\t\t  // times = [[2,1,1],[2,3,1],[3,4,1]]\n\t\t  // adj = 2=>{(1,1), (3,1)}, 3=>{(4,1)}\n\n\t\t  // Till we visited all the vertex in the graph\n\t\t while (!pq.empty()) {\n\t\t\t pair<int, int>p = pq.top();\n\t\t\t pq.pop();\n\t\t\t int u = p.second;\n\t\t\t // Main Dijistra\'s Algorithm starts here updating distance of each vertex to minimum\n\t\t\t for (auto it = adj[u].begin(); it != adj[u].end(); it++) {\n\t\t\t\tint v = it->first;\n\t\t\t\tint w = it->second;\n\t\t\t\tif (dist[v] > dist[u] + w) {\n\t\t\t\t\t\tdist[v] = dist[u] + w;\n\t\t\t\t\t\tpq.push(make_pair(dist[v], v));\n\t\t\t\t}\n\t\t\t  }\n\t\t\t}\n\n\t\t  // Maximum value of dist will be the max value of time taken to visit all vertex in graph\n\t\t  int t = 0;\n\t\t  for (int i = 1; i <= N; i++)\n\t\t\t t = max(t, dist[i]);\n\n\t\t  // if not possible return -1 else return t \n\t\t  return t == INT_MAX ? -1 : t;\n\t\t}\n\t};\n```
[]