思路：
反向建边 看能到哪儿再正向搞
我傻乎乎地最后竟然用了Dijkstra 普通BFS就可以//By SiriusRen#include#include #include #include using namespace std;#define N 250000struct node{ int at,weight;friend bool operator < (node a,node b){ return a.weight>b.weight;}}jy,tmp;priority_queue pq;int n,first[N],next[N],v[N],tot=0,start,end,dis[N],rec[N],m,xx[N],yy[N];bool vis[N];void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}void dfs(int x){ for(int i=first[x];~i;i=next[i]){ if(!vis[v[i]]){ vis[v[i]]=1; dfs(v[i]); } }}bool check(int x){ for(int i=first[x];~i;i=next[i]){ if(!vis[v[i]])return 0; } return 1;}void Dijkstra(int x){ memset(dis,0x3f,sizeof(dis)); dis[x]=0; jy.at=x;jy.weight=0; pq.push(jy); while(!pq.empty()){ jy=pq.top();pq.pop(); if(rec[jy.at])continue; rec[jy.at]=1; for(int i=first[jy.at];~i;i=next[i]){ if(!rec[v[i]]&&dis[v[i]]>dis[jy.at]+1&&vis[v[i]]&&check(v[i])){ dis[v[i]]=dis[jy.at]+1; tmp.at=v[i]; tmp.weight=jy.weight+1; pq.push(tmp); } } }}int main(){ memset(first,-1,sizeof(first)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&xx[i],&yy[i]),add(yy[i],xx[i]); scanf("%d%d",&start,&end); vis[end]=1;dfs(end); memset(first,-1,sizeof(first)); tot=0; for(int i=1;i<=m;i++)add(xx[i],yy[i]); Dijkstra(start); if(dis[end]<0x3ffffff)printf("%d",dis[end]); else printf("-1");}
