/ zzf / 讨论 / 问答 /

zzf寻找道路咋做

啊啊啊啊啊

1 条评论

  • @ 2018-09-10 20:01:49

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #define N 10001
    #define inf 100000001
    using namespace std;
    int n,m,d[N];
    int a,b;
    struct zzf{
    int cot;
    int cnt;
    int boo;
    int nex[N/4];
    int pre[N/4];
    }zzf_[N];

    int cut(int i){
    if(zzf_[i].cot==0 && i!=b){
    for(int j=1;j<=zzf_[i].cnt;j++){
    zzf_[zzf_[i].pre[j]].cot=0;
    }

    zzf_[i].boo=1;
    }
    else{
    for(int x=1;x<=zzf_[i].cnt;x++)
    cut(zzf_[i].nex[x]);
    }
    }

    int spfa(int s){
    d[s]=0;
    queue <int> q;
    q.push(s);
    while(!q.empty()){
    int x=q.front();
    q.pop();
    for(int i=1;i<=zzf_[x].cot;i++){
    q.push(zzf_[x].nex[i]);
    if(d[zzf_[x].nex[i]]>d[x]+1 && zzf_[x].boo==0){
    d[zzf_[x].nex[i]]=d[x]+1;
    q.push(zzf_[x].nex[i]);
    }
    }

    }

    }

    int main(void){

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    d[i]=inf;

    for(int i=1;i<=m;i++){
    cin>>a>>b;
    zzf_[a].cot++;
    zzf_[b].cnt++;
    zzf_[a].nex[zzf_[a].cot]=b;
    zzf_[b].pre[zzf_[b].cnt]=a;
    }
    cin>>a>>b;
    cut(a);
    cut(a);
    spfa(a);
    if(d[b]==inf) printf("-1\n"); else printf("%d\n",d[b]);
    return 0;
    }

  • 1