题解 P2296 【寻找道路】

· · 题解

并不需要BFS

读题后发现，不能走的点为除终点以外出度为0的点，以及与这些点直接相连的点。

那就删了就好了。。。。

设一个数组del[i]表示i节点已被删除，扫一下就好了。。

注意为了避免删除间接与那些点相连的点，可以再记录一下嘛。。

然后SPFA就好了

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#define maxn 10005
#define inf dis[10004]
using namespace std;
inline void read(int &num){
    char c;num=0;
    while((c=getchar())==' '||c=='\r'||c=='\n');
    num+=c-48;
    while((c=getchar())>=48&&c<=57)num=num*10+c-48;
    return;
}
struct Edges{int from,to;};
vector<Edges>edge;
vector<int>G[maxn];
inline void addedge(int u,int v){
    edge.push_back((Edges){u,v});
    G[u].push_back(edge.size()-1);
    return;
}
int n,m,s,t,outd[maxn];
bool del[maxn],mark[maxn];
bool vis[maxn];int dis[maxn];
int spfa(int U,int V){
    queue<int>q;
    memset(dis,0x7f,sizeof(dis));
    dis[U]=0;
    q.push(U);
    Edges e;int u,tmp;
    while(!q.empty()){
        u=q.front();q.pop();
        vis[u]=0;
        tmp=G[u].size();
        for(int j=0;j<tmp;++j){
            e=edge[G[u][j]];
            if(dis[e.to]>dis[e.from]+1&&!del[e.to]&&!del[e.from]){
                dis[e.to]=dis[e.from]+1;
                if(!vis[e.to]){
                    vis[e.to]=1;
                    q.push(e.to);
                }
            }
        }
    }
    if(dis[V]<inf)return dis[V];
    return -1;
}
int main(){
    read(n);read(m);
    int x,y,z;
    for(int i=1;i<=m;++i){
        read(x);read(y);
        if(x!=y){
            addedge(x,y);
            ++outd[x];
        }
    }
    read(s);read(t);
    ++outd[t];
    for(int i=1;i<=n;++i)
        if(!outd[i]) del[i]=1;
    int tmp;
    for(int i=1;i<=n;++i){
        tmp=G[i].size();
        bool flag=0;int v;
        for(int j=0;j<tmp;++j){
            if(del[edge[G[i][j]].to]&&!mark[edge[G[i][j]].to]){
                flag=1;
                break;
            }
        }
        if(flag)del[i]=mark[i]=1;
    }
    cout<<spfa(s,t);
    return 0;
}