```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int INF=1e9+10;
int n,m,s,t;
map<pair<int,int>,bool> ma;
vector<int> g[N];
int dis[N],vis[N],vis2[N],vis3[N];
struct node{
int v,w;
bool operator<(const node &r) const{
return r.w<w;
}
};
priority_queue<node> q;
void dfs(int u){
// cout<<u<<'\n';
vis3[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(!vis3[v]) dfs(v);
if(vis[u]==-2) continue;
if(vis[u]==0){
if(vis[v]==-2) vis[u]=1;
else vis[u]=vis[v];
}
if(vis[u]==1){
if(vis[v]==-1){
vis[u]=-2;
}
}
if(vis[u]==-1){
if(vis[v]==1||vis[v]==-2){
vis[u]=-2;
}
}
}
if(g[u].size()==0) vis[u]=-1;
}
void dijkstra(){
for(int i=1;i<=n;i++){
dis[i]=INF;
}
dis[s]=0;
q.push(node{s,0});
while(!q.empty()){
node temp=q.top();
q.pop();
int u=temp.v;
vis2[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(dis[v]>dis[u]+1&&((!vis2[v])&&vis[v]==1)){
dis[v]=dis[u]+1;
q.push(node{v,dis[v]});
}
}
}
}
int main(){
// freopen("p2296.txt","r",stdin);
// freopen("p2296.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
if(u==v) continue;
if(ma[make_pair(u,v)]) continue;
ma[make_pair(u,v)]=1;
g[u].push_back(v);
}
cin>>s>>t;
vis[t]=1;
vis3[t]=1;
dfs(s);
// cout<<1<<'\n';
dijkstra();
cout<<(dis[t]==INF?-1:dis[t])<<'\n';
return 0;
}
```
我也30pts,你也是想正着搜吧?
这样可能有环,就挂了。
by Clarence_Zhu @ 2023-11-09 09:33:08
我还太弱,布吉岛该怎么处理环。。。。
大佬如果调出来可以教教我。
by Clarence_Zhu @ 2023-11-09 09:35:32
这份变成80pts了
```cpp
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define fo(i,a,b) for(int i=(a);i<(b);++i)
#define PII pair<int,int>
#define LL long long
using namespace std;
const int N=1e4+5;
int n,m;
vector<int> G[N];
int vis[N];
int S,T;
bool ke[N];
bool dfs(int u){
if(u==T){
vis[u]=1;
return true;
}
vis[u]=-1;
bool flag= false;
for(auto &v:G[u]){
if(vis[v]==0&&dfs(v)) flag=true;
if(vis[v]==1) flag=true;
}
if(flag==true){
vis[u]=1;
return true;
}
return false;
}
int bfs(){
memset(vis,0,sizeof vis);
queue<PII> q;
q.push({S,0});vis[S]=1;
while(!q.empty()){
PII u=q.front();q.pop();
if(u.first==T) return u.second;
for(auto v:G[u.first]) if(ke[v]==true) {
if(vis[v]) continue;
q.push({v,u.second+1});
vis[v]=1;
}
}
return -1;
}
int main(){
std::ios::sync_with_stdio(0);
cin>>n>>m;
rep(i,1,m){
int x,y;
cin>>x>>y;
G[x].push_back(y);
}
cin>>S>>T;
//判断每个点与终点联通性
rep(i,1,n){
dfs(i);
}
for(int i = 1; i <= n; i++){
//cout << vis[i] << endl;
}
//判断合法点
rep(u,1,n){
bool flag=true;
for(auto &v:G[u]){
if(vis[v]==-1){
flag=false;
break;
}
}
ke[u]=flag;
}
cout<<bfs();
}
```
by bsjsaikou10 @ 2023-11-09 10:05:12
bfs反向去做可以覆盖到与T相连的所有点,而dfs去做,dfs只会走出一颗树,可能有些边走不到,或者说是后效性的原因?
by bsjsaikou10 @ 2023-11-09 10:19:03
@[bsjsaikou10](/user/824941) 或者你反向做一下试试
by bsjsaikou10 @ 2023-11-09 10:21:47