C++ Dijkstra Algorithm and BFS
Solution 1: Dijkstra Algorithm\n\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int N, int K) {\n        \n        vector<vect
Solution 1: Dijkstra Algorithm\n```\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int N, int K) {\n        \n        vector<vector<pair<int,int>>> G(N);\n        for(auto itr: times)\n            G[itr[0]-1].push_back({itr[1]-1,itr[2]});\n        \n        vector<int> timetaken(N,INT_MAX);\n        return Dijkstra(K-1,G,N,timetaken);\n    }\n    int Dijkstra(int s, vector<vector<pair<int,int>>> &G, int N, vector<int> &timetaken)\n    {\n        priority_queue< pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>> > pq;\n        pq.push({0,s});\n        timetaken[s]=0;\n        while(!pq.empty())\n        {\n            int time=pq.top().first;\n            int source=pq.top().second;\n            pq.pop();\n            for(auto itr: G[source])\n            {\n                if(timetaken[itr.first]>(time+itr.second))\n                {\n                    pq.push({time+itr.second,itr.first});\n                    timetaken[itr.first]=time+itr.second;\n                }\n            }\n        }\n        \n        int max_val=0;\n        for(int i=0; i<N; ++i)\n        {\n            if(timetaken[i]==INT_MAX)\n                return -1;\n            max_val=max(max_val,timetaken[i]);\n        }\n        return max_val;\n    }\n};\n```\nSolution 2: BFS\n```\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int N, int K) {\n        \n        vector<vector<pair<int,int>>> G(N);\n        for(auto itr: times)\n            G[itr[0]-1].push_back({itr[1]-1,itr[2]});\n        \n        vector<int> timetaken(N,INT_MAX);\n        return BFS(K-1,G,N,timetaken);\n    }\n    int BFS(int s, vector<vector<pair<int,int>>> &G, int N, vector<int> &timetaken)\n    {\n        queue<pair<int,int>> pq;\n        pq.push({0,s});\n        timetaken[s]=0;\n        while(!pq.empty())\n        {\n            int time=pq.front().first;\n            int source=pq.front().second;\n            pq.pop();\n            for(auto itr: G[source])\n            {\n                if(timetaken[itr.first]>(time+itr.second))\n                {\n                    pq.push({time+itr.second,itr.first});\n                    timetaken[itr.first]=time+itr.second;\n                }\n            }\n        }\n        \n        int max_val=0;\n        for(int i=0; i<N; ++i)\n        {\n            if(timetaken[i]==INT_MAX)\n                return -1;\n            max_val=max(max_val,timetaken[i]);\n        }\n        return max_val;\n    }\n};\n```
['C', 'Heap (Priority Queue)']