Submission #41559305

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> e(n+m);
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        int x = i + m;
        for (int j = 0; j < a; j++)
        {
            int s;
            cin >> s;
            --s;
            e[s].push_back(x);
            e[x].push_back(s);
        }
    }
    constexpr int inf = 1e9;
    queue<int> q;
    vector<int> d(n+m, inf);
    q.push(0);
    d[0] = 0;
    while(not q.empty())
    {
        int x = q.front();q.pop();
        if(x == m-1)
        {
            cout << d[x] / 2 - 1 << endl;
            return;
        }
        for(int y: e[x])
        {
            if(d[y] == inf)
            {
                q.push(y);
                d[y] = d[x] + 1;
            }
        }
    }
    cout << -1 << endl;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
}

Submission Info

Judge Result