题解 P2296 【寻找道路】

会炸的甲烷 · 2017-09-25 17:10:19 · 题解

看大佬都是spfa

萌新水一波bfs

#include<bits/stdc++.h>
using namespace std;
vector<int>cun[10005];
vector<int>fan[10005];
int cha[10005],dis[10005];//cha是剪枝数组，dis记录距离
int n,m,s,t,len=0;
vector<int>::iterator it;
void dfs(int x) {
    vector<int>::iterator i;
    for(i=fan[x].begin() ; i!=fan[x].end(); i++) {
        if(!cha[*i]) {
//            if(cha[*i]==1)continue;
            cha[*i]=1;
            dfs(*i);
        }
    }

}//剪枝

void bfs() {
    queue<int> fuzhu;
    fuzhu.push(s);
    while(!fuzhu.empty()){
        int tmp;
        tmp=fuzhu.front();
        fuzhu.pop();
        if(!cha[tmp])continue;
        vector<int>::iterator i;
        for(i=cun[tmp].begin() ; i!=cun[tmp].end() ; i++) {
            if(dis[*i]!=0) continue;
            if(!cha[*i])continue;
            fuzhu.push(*i);
            dis[*i]=dis[tmp]+1;//更新距离
        }
    }

}//因为边的权值是一，所以bfs第一次找到终点就是最短路

int main() {
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        int a,b;
        cin>>a>>b;
        cun[a].push_back(b) ;
        fan[b].push_back(a);
    }
    memset(cha,0,sizeof(cha));
    memset(dis,0,sizeof(dis));
    cin>>s>>t;
    cha[t]=1;
    dfs(t);
//    printf("%d*****\n",cha[6]);
    for(int i=1; i<=n; i++) {
        if(!cha[i]) {
            vector<int>::iterator j;
            for(j=fan[i].begin() ; j!=fan[i].end() ; j++) {
                cha[*j]=2;
            }
        }
    }
    for(int i=1;i<=n;i++) if(cha[i]==2) cha[i]=0;
    bfs();
    if(dis[t]==0)cout<<-1;
    else cout<<dis[t];
}