Minimum Distance in a Star Graph BFS/康托展开 2017 ACM-ICPC 亚洲区（南宁赛区）网络赛

题目链接

---

模拟+BFS+康拓展开,此题的数据比较水,如果n为9就GG了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> mm[500005];
int vis[500005];
int n;
ll sum =0;
int a[11];
int b[11];
int  fac[] = {1,1,2,6,24,120,720,5040,40320}; //i的阶乘为fac[i]



// 康托展开-> 表示数字a是 a的全排列中从小到大排，排第几
// n表示1~n个数  a数组表示数字。
int kangtuo()
{
    int i,j,t,sum;
    sum=0;
    for( i=0; i<n ;++i)
    {
        t=0;
        for(j=i+1;j<n;++j)
            if( a[i]>a[j] )
                ++t;
        sum+=t*fac[n-i-1];
    }
    return sum+1;
}

struct NODE
{
    int x;
    int step;
};



int  bfs(int ss,int tt)
{
    queue <NODE> que;
    memset(vis,0,sizeof(vis));
    NODE cur,next;
    cur.x = ss;
    cur.step = 0;

    vis[cur.x] = 1;

    que.push(cur);

    while(!que.empty())
    {
        cur = que.front();
        que.pop();
        if(cur.x==tt)
        {
            return cur.step;
        }

        for(int i=0;i<mm[cur.x].size();i++)
        {
            if(vis[ mm[cur.x][i]]) continue;
            next = cur;
            next.x = mm[cur.x][i];
            next.step +=1;
            vis[next.x] = 1;
            que.push(next);
        }
    }

}

int main()
{
//    freopen("data.txt","r",stdin);
    scanf("%d",&n);

    for(int i=0;i<n;i++)
    {
        a[i] = b[i] = i+1;
    }
    sum = 1;
    for(int i=1;i<=n;i++)
    {
        sum *= i;
    }

    for(int i=1;i<=sum;i++)
    {
        for(int j=0;j<n;j++)
        {
            a[j] = b[j];
        }
        for(int j=1;j<n;j++)
        {
            swap(a[0],a[j]);
            ll to = kangtuo();
            mm[i].push_back(to);
            mm[to].push_back(i);
            swap(a[0],a[j]);
        }
        next_permutation(b,b+n);
    }

    ll s,t;
    for(int i=0;i<5;i++)
    {
        scanf("%lld%lld",&s,&t);
        int dig=n-1;
        while(s)
        {
            a[dig--] = s%10;
            s/=10;
        }
        s= kangtuo();

        dig=n-1;
        while(t)
        {
            a[dig--] = t%10;
            t/=10;
        }
        t= kangtuo();

        printf("%d\n",bfs(s,t));
    }


    return 0;
}