30分求调教

P2296 [NOIP2014 提高组] 寻找道路

```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


|