- 问答
- @ 2018-09-10 19:56:54
啊啊啊啊啊
1 条评论
- 
  PA_lotusbl LV 5 MOD @ 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