萌新刚学图论
  • 板块P1346 电车
  • 楼主da_ke
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/8/14 20:39
  • 上次更新2023/11/3 03:46:48
查看原帖
萌新刚学图论
766675
da_ke楼主2023/8/14 20:39
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)

using namespace std;

int f[124][124];
int n,a,b;
const int INF=0x3f3f3f;

int main(){
    memset(f,INF,sizeof(f));
    cin>>n>>a>>b;
    rep(i,1,n){
        int k;
        cin>>k;
        rep(j,1,k){
            int to;
            cin>>to;
            if(j==1) 
                f[i][to]=0;
            else
                f[i][to]=1;
        }
    }
    rep(k,1,n)
        rep(x,1,n)
            rep(y,1,n)
                if(x!=y)
                    f[x][y]=min(f[x][y],f[x][k]+f[k][y]);
                else
                    f[x][y]=0;
    if(f[a][b]==INF) 
        cout<<-1;
    else 
        cout<<f[a][b];
}
2023/8/14 20:39
加载中...