- 图论
- 2019-11-12 17:24:01 @
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0') f^=(c=='-'),c=getchar();
while(c>'/') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
return f?x:-x;
}
vector<int>e1[10010],e2[10010];
int bo[10010],vs[10010];
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
e1[u].push_back(v);
e2[v].push_back(u);
}
queue<int> q1;
s=read();
t=read();
bo[t]=1;
q1.push(t);
while(!q1.empty()){
int no=q1.front();
q1.pop();
for(int i=0;i<e2[no].size();i++){
int to=e2[no][i];
if(!bo[to]){
q1.push(t);
bo[to]=1;
}
}
}
if(!bo[s]){
puts("-1");
return 0;
}
queue<int> q2;
vs[s]=1;
q2.push(s);
while(!q2.empty()){
int no=q2.front();
q2.pop();
for(int i=0;i<e1[no].size();i++){
int to=e1[no][i];
if(bo[to]&&!vs[to]){
q2.push(t);
vs[to]=vs[no]+1;
}
}
}
printf("%d\n",vs[t]-1);
return 0;
}
2 条评论
-
xiebofan LV 1 MOD @ 2019-11-12 20:07:15
捞出来了吗?
-
2019-11-12 17:24:17@
求高一捞题
- 1