题目：
先从终点dfs一下能走到终点的，然后从起点bfs即可。O(n+m)。
#include#include #include #include using namespace std;const int N=1e4+5,M=2e5+5;int n,m,hd[N],xnt,to[M],nxt[M],st,en,thd[N],tnt,tto[M],txt[M];int q[N],he,tl,dis[N],k;bool vis[N],flag,fw[N];int rdn(){ int ret=0,fx=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') fx=-1; ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return ret*fx;}void add(int x,int y){ to[++xnt]=y; nxt[xnt]=hd[x]; hd[x]=xnt;}void adt(int x,int y){ tto[++tnt]=y; txt[tnt]=thd[x]; thd[x]=tnt;}void dfs(int cr){ vis[cr]=1; for(int i=thd[cr],v;i;i=txt[i]) if(!vis[tto[i]]) dfs(tto[i]);}int main(){ n=rdn(); m=rdn(); for(int i=1,x,y;i<=m;i++) { x=rdn(); y=rdn(); add(x,y); adt(y,x); } st=rdn(); en=rdn(); dfs(en); if(!vis[st])flag=1; for(int i=hd[st];i;i=nxt[i]) if(!vis[to[i]]){flag=1;break;} if(flag){puts("-1");return 0;} q[tl=1]=st; fw[st]=1; while(he<=tl) { k=q[++he]; for(int i=hd[k],v;i;i=nxt[i]) if(vis[v=to[i]]&&!fw[v]) { flag=0; fw[v]=1; for(int j=hd[v];j;j=nxt[j]) if(!vis[to[j]]){flag=1;break;} if(!flag) { dis[v]=dis[k]+1; q[++tl]=v; if(v==en){printf("%d\n",dis[v]);return 0;} } } } puts("-1"); return 0;}