Simple and easy to understand using floyd warshal
IntuitionThe problem is about counting the number of node pairs (i,j) at each shortest path distance in a graph of n nodes. The graph is initially a linear chai
# Intuition
The problem is about counting the number of node pairs (i,j) at each shortest path distance in a graph of n nodes. The graph is initially a linear chain (1—2—3—...—n), but we add an extra edge between nodes x and y, creating a shortcut. We then compute the shortest paths between all node pairs and count their frequencies.

# Approach
Graph Representation:
Use an adjacency matrix (grid) initialized with a large value (100000 to represent infinity).
Connect consecutive nodes (j ↔ j+1 with weight 1).
Add the extra shortcut edge x ↔ y with weight 1.

Floyd-Warshall Algorithm:
Compute the shortest path between all pairs using dynamic programming:
grid[i][j]=min(grid[i][j],grid[i][k]+grid[k][j])
This ensures that the shortest distance is updated iteratively for all pairs.

Counting Distances:
Iterate through all distinct pairs (i, j) and count how many pairs exist for each distance value.

# Complexity
- Time complexity: O(n^3)

- Space complexity: O(n^2)

# Code
```cpp []
class Solution {
public:
    vector<int> countOfPairs(int n, int x, int y) {
        vector<vector<int>> grid(n+1, vector<int>(n+1, 100000));
        for(int j=1; j<n; j++){
            grid[j][j+1] = 1;
            grid[j+1][j] = 1;
        }
        grid[x][y] = 1;
        grid[y][x] = 1;
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
                }
            }
        }
        vector<int> result(n);
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i!=j){
                    int val = grid[i][j];
                    result[val-1]++;
                }
            }
        }
        return result;
    }
};
```
['Graph', 'Shortest Path', 'C++']