[NOIP2014]寻找道路

思路

首先要把一些不满足条件的点剔除掉，然后就是求最短路的事情了。
要找不满足条件的点，可以反向建边，然后从终点出发，标记每一个经过的点。那么剩下没有走过的点就可以去掉了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005,maxm=200005;

int cant[maxn],vis[maxn],dis[maxn];
int n,m,s,t,e,u,v;

struct E{
    int next,to;
}edge[maxm],edge2[maxm];

struct node{
    int n,w;
};
bool operator<(const node a,const node b){
    return a.w<b.w;
}

void read(int &data){
    int flag=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') flag=-flag;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    data=flag*x;
}

priority_queue<node>pq;
int head[maxn],head2[maxn],cnt=0,cnt2=0;
inline void addedge(int from,int to){
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;

    edge2[++cnt2].next=head2[to];
    edge2[cnt2].to=from;
    head2[to]=cnt2;
}

void dfs(int x){
    vis[x]=1;
    for(int i=head2[x];i;i=edge2[i].next){
        int y=edge2[i].to;
        if(!vis[y]){
            dfs(y);
        }
    }
}

void dijistra(int s){
    memset(dis,127/3,sizeof(dis));
    if(cant[s]) return;
    pq.push((node){s,0});
    dis[s]=0;
    while(!pq.empty()){
        node fro=pq.top();
        pq.pop();
        if(dis[fro.n]!=fro.w) continue;
        for(int i=head[fro.n];i;i=edge[i].next){
            int y=edge[i].to;
            if(cant[y]) continue;
            if(dis[y]>dis[fro.n]+1){
                dis[y]=dis[fro.n]+1;
                pq.push((node){y,dis[y]});
            }
        }
    }
}
int main(){
    read(n);read(m);
    for(int i=1;i<=m;i++){
        read(u);read(v);
        if(u==v)continue; //去重边
        addedge(u,v); //建反向边
    }
    read(s);read(t);
    dfs(t);  //从终点出发，找出无法到达的点
    for(int i=1;i<=n;i++)
        if(!vis[i]) cant[i]=1;
    for(int i=1;i<=n;i++){
        if(!vis[i]) continue; 
        int flag=0;
        for(int j=head[i];j;j=edge[j].next){
            int y=edge[j].to;
            if(!vis[y]){ //如果出点被剔除，那么该点也被剔除
                flag=1;
                break;
            }
        }
        if(flag) cant[i]=1; //该数组存储最终剔除的结点
    }
    dijistra(s); //找最短路
    if(dis[t]>1e6+7) cout<<-1<<endl;
    else cout<<dis[t]<<endl;
    return 0;
}