- 问答
- 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