156312025-02-21 12:31:03999A lehető legkevesebb metróval utazás (40 pont)cpp17Wrong answer 10/40354ms32000 KiB
// Source: https://usaco.guide/general/io

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

const int INF=1e12;

int main() {
    int n,m,ind,erk;cin>>n>>m>>ind>>erk;
    vector<vector<int>> v(n);
    vector<vector<int>> a(m);
    ind--;erk--;
    for(int i = 0;i<n;i++){
        int x;cin>>x;
        for(int j = 0;j<x;j++){
            int b;cin>>b;
            a[--b].push_back(i);
        }
    } 
    for(int i = 0;i<m;i++){
        for(int j = 0;j<a[i].size();j++){
            for(int k = 0;k<j;k++){
                v[a[i][k]].push_back(a[i][j]);
                v[a[i][j]].push_back(a[i][k]);
            }
        }
    }
    queue<int> q;
    vector<int> dis(n,INF);
    for(int i : a[ind]){
        q.push(i);
        dis[i]=1;
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i : v[u]){
            if(dis[i]==INF){
                dis[i]=dis[u]+1;
                q.push(i);
            }
        }
    }
    int ans=0;
    for(int i : a[erk]){
        ans=max(ans,dis[i]);
    }
    cout<<ans<<endl;
}
SubtaskSumTestVerdictTimeMemory
base10/40
1Wrong answer0/01ms316 KiB
2Wrong answer0/06ms1076 KiB
3Wrong answer0/21ms316 KiB
4Partially correct1/21ms508 KiB
5Partially correct1/21ms576 KiB
6Wrong answer0/21ms508 KiB
7Wrong answer0/22ms316 KiB
8Partially correct1/22ms564 KiB
9Partially correct1/24ms564 KiB
10Wrong answer0/24ms564 KiB
11Partially correct1/22ms316 KiB
12Partially correct1/27ms1076 KiB
13Partially correct1/27ms1108 KiB
14Partially correct1/26ms1076 KiB
15Runtime error0/2337ms32000 KiB
16Runtime error0/2354ms32000 KiB
17Runtime error0/2351ms32000 KiB
18Runtime error0/2338ms32000 KiB
19Partially correct1/24ms624 KiB
20Wrong answer0/26ms820 KiB
21Partially correct1/23ms564 KiB
22Wrong answer0/26ms1076 KiB