题解 P2296 【寻找道路】

· · 题解

//看到下面的大佬都是反向建图，身为蒟蒻的我，只能用普通方法来水一发

//首先看题意，他相当于是要找从一个点到另一给点的最小步数，因为边的权值都是一，所以要把不能走的点去除

//因为它不仅要去掉不直接相连的，还要去掉与不直接相连的相连的

//这就有点麻烦了，本来以为直接用循环去找会出错，但是竟然A了，让我很意外。

//剩下的就是心酸和泪水，为了A掉，我不幸的WA了25遍，只因为memset（流泪）

//话不多说，剩下的提交代码吧（注释在里面）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>//以上为缺省源帮打，可以直接用<bits/stdc++.h>代替 
using namespace std;
inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}//上面是快读，可以提供借鉴，也可以忽略掉。
int n,m,rd[10001],cd[10001],a,b,s,t,ans[10001];//n,m按照题目要求定义，s，t表示起点和终点，ans数组记录答案，rd没什么用，懒得删，cd记录点的出度 ，a，b是需要输入的。 
bool road[10001][10001],f[10001];//road数组表示是否相连，f表示是不是“叛徒 ” 
queue<int>Q;//队列 
void pd() {
    while(Q.empty() == 0) {
        int q=Q.front();
        Q.pop();
        for(int i=1; i<=n; ++i) {
            if(f[i]==0 && road[q][i]==1 && ans[i]>ans[q]+1) {
                ans[i]=ans[q]+1;
                Q.push(i);
                if(i==t) {
                    cout<<ans[i];
                    return;
                }
            }
        }
    }
    cout<<"-1";
    return ;
}//这个是用来判断的，只要队列里的元素不空，表示可以继续走，直到找到终点或者队列为空。 
int main() {
    memset(ans,9999999,sizeof(ans));//这里卡了我好久好久，好像让我错了十几遍，都没发现是这里的问题，。 
    n=read();
    m=read();//读入点数和边数 
    for(int i=1; i<=m; ++i) {
        a=read();
        b=read();
        road[a][b]=1;
        cd[a]++;
        rd[b]++;
    }//读入相连的点，顺便把入度和出度记录一下。 
    s=read();
    t=read();//读入起点和终点 
    for(int i=1; i<=n; ++i) {
        if(cd[i]==0&&i!=t) {
            f[i]=1;
            for(int j=1; j<=n; ++j) {
                if(road[j][i]==1) {
                    f[j]=1;
                }
            }
        }
    }//这是找叛徒和敌人的地方。 
    ans[s]=0;//吧起点的答案设置成0 
    Q.push(s);//把起点入队 
    pd();//进行判断 
    return 0;//带泪结束
}

//还希望能够通过