Mike and Shortcuts

建图跑个bfs就好了= - =

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int>v[N];
int vis[N],dis[N];
queue<int>q;
void bfs()
{
    while(q.size())
    {
        int temp=q.front();
        q.pop();
        for(int i=0;i<v[temp].size();i++)
        {
            int pos=v[temp][i];
            if(vis[pos]) continue;
            vis[pos]=1;
            q.push(pos);
            dis[pos]=dis[temp]+1;
           //            if(pos==6) cout<<temp<<' '<<dis[pos]<<endl;
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        v[i].push_back(x);
    }
    for(int i=2;i<=n;i++)
    {
        v[i].push_back(i-1);
        v[i-1].push_back(i);
    }
    q.push(1);
    dis[1]=0;vis[1]=1;
    bfs();
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }puts("");
    return 0;
}