Using Dijkstra |C++
Intuition\n Describe your first thoughts on how to solve this problem. \nYou need shortest distance from each node to every other node and that will serve as th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nYou need shortest distance from each node to every other node and that will serve as the minimum distance (k) required to reach that node. Use any shortest distance algorithm to do so and create an ans array that stores the number of nodes that require minimum k distance.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCreate an adjaceny list with weights 1 and call dijkstra for every node in the graph.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(ElogV)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    void dijkstraShortestDistance( int src,vector<int> &dist,unordered_map<int,list<pair<int,int>>> &adjlist) {\n\t\t\n\t\tset<pair<int,int> > st;\n\t\tst.insert({0,src});\n\t\tdist[src] = 0;\n\t\twhile(!st.empty()) {\n\t\t\tauto topElement = st.begin();\n\t\t\tpair<int, int> topPair = *topElement;\n\t\t\tint topDist = topPair.first;\n\t\t\tint topNode = topPair.second;\n\t\t\tst.erase(st.begin());\n\t\t\tfor(pair<int,int> nbrPair: adjlist[topNode]) {\n\t\t\t\tint nbrNode = nbrPair.first;\n\t\t\t\tint nbrDist = nbrPair.second;\n\t\t\t\tif(topDist + nbrDist < dist[nbrNode]) {\n\t\t\t\t\tauto previousEntry = st.find({dist[nbrNode], nbrNode});\n\t\t\t\t\tif(previousEntry != st.end()) {\n\t\t\t\t\t\tst.erase(previousEntry);\n\t\t\t\t\t}\n\t\t\t\t\tdist[nbrNode] = topDist + nbrDist;\n\t\t\t\t\tst.insert({dist[nbrNode], nbrNode});\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\n\n\n\t}\n    vector<int> countOfPairs(int n, int x, int y) {\n        unordered_map<int,list<pair<int,int>>>adj;\n        for(int i=1;i<=n-1;i++)\n        {\n            adj[i].push_back({i+1,1});\n            adj[i+1].push_back({i,1});\n        }\n        adj[x].push_back({y,1});\n        adj[y].push_back({x,1});\n        vector<int>ans(n+1,0);\n        for(int i=1;i<=n;i++)\n        {\n            vector<int> dist(n+1, INT_MAX);\n\n            dijkstraShortestDistance(i,dist,adj);\n            for(int i=1;i<=n;i++)\n            {\n                cout<<dist[i]<<" ";\n                int mindistance=dist[i];\n                ans[mindistance]++;\n            }\n            cout<<endl;\n\n\n\n        }\n        vector<int>onebased(n,0);\n        int j=0;\n        for(int i=1;i<=n;i++)\n        {\n            onebased[j]=ans[i];\n            j++;\n        }\n        return onebased;\n    }\n};\n```
['C++']