Shortest Path Model
IntuitionGraphs
Dijkstra's algorithm
HashingApproachc++Complexity

Time complexity:
O(n^2logn).


Space complexity:
O(n^2)

Code
# Intuition
Graphs
**Dijkstra's algorithm**
Hashing

# Approach
**c++**

# Complexity
- Time complexity:
    
    O(n^2logn).


- Space complexity:
  O(n^2)

# Code
```cpp []
class Solution {
public:
    map<int, vector<pair<int, int>>> mp;

    void solve(int node, vector<pair<int, int>> adj[], int n) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, node});
        
        vector<int> dist(n + 1, INT_MAX);
        dist[node] = 0;

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();

            for (auto [v, weight] : adj[u]) {
                if (dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (dist[i] != INT_MAX && dist[i] != 0) {
                mp[dist[i]].emplace_back(node, i);
            }
        }
    }

    vector<int> countOfPairs(int n, int x, int y) {
        vector<pair<int, int>> adj[n + 1];
        for (int i = 1; i < n; i++) {
            adj[i].push_back({i + 1, 1});
            adj[i + 1].push_back({i, 1});
        }
        adj[x].push_back({y, 1});
        adj[y].push_back({x, 1});

        for (int i = 1; i <= n; i++) {
            solve(i, adj, n);
        }

        vector<int> v(n+1,0);
        for (auto it : mp) {
            if (it.first > 0 && it.first <= n) {
                v[it.first] = static_cast<int>(it.second.size());
            }
        }
        vector<int>ans;
        for(int i=1;i<=n;i++){
        ans.push_back(v[i]);
        }
        return ans;
    }
};

```
['Graph', 'Shortest Path', 'C++']