Line++

Line++

Problem Statement

We have an undirected graph GG with NN vertices numbered 11 to NN and NN edges as follows:

• For each i=1,2,...,N−1, there is an edge between Vertex i and Vertex i+1.
• There is an edge between Vertex X and Vertex Y.

For each k=1,2,...,N−1, solve the problem below:

• Find the number of pairs of integers (i,j)(1≤i<j≤N)such that the shortest distance between Vertex i and Vertex j in G is k.

Constraint

• \(3≤N≤2×10^3\)
• \(1≤X,Y≤N\)
• \(X+1<Y\)
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

For each k=1,2,...,N−1 in this order, print a line containing the answer to the problem.

Idea

类似于floyd算法，但是只需要考虑经过x，y时的路程是否更小即可

Code

/******************************************
/@Author: LeafBelief
/@Date: 2020-04-07
/@Remark:    
/@FileName: changeflyord
******************************************/
#include <bits/stdc++.h>
#define CSE(x,y) memset(x,y,sizeof(x))
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;

const int maxn = 2010;
int dis[maxn][maxn], n, x, y;
int ans[maxn];

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    #endif
    FAST;
    cin >> n >> x >> y;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dis[i][j] = dis[j][i] = abs(i -j);
        }
    }
    dis[x][y] = dis[y][x] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dis[i][j] = min(dis[i][j], dis[i][x] + dis[y][j] + 1);
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            ans[dis[i][j]]++;
    for(int i = 1; i < n; i++)
        cout << ans[i] << endl;
    return 0;
}