题解 P2296 【寻找道路】

· · 题解

我不知道我是不是独创了一种新的做法。。 我的思路是反向建边，因为想一下，如果你从起点直接走向终点，肯定有好多情况的啊，出题人卡的就是这种，所以你反向建一下边，会省去好多卡你的数据，是不是很玄学。。最后从终点开始遍历到起点。这里我用的bfs，因为它的性质就是只要搜索到，就是最优解。lalalala

然后干扰的情况，你把所有除了终点的入度为零的点所连的点，就是题目中不能走的点，全部染色，就符合了第一个条件了。当你把这个点染色，他所在的路径就不能被走了，那你就放心大胆的暴力，lalalala

代码很简单，hahahahaha

#include <bits/stdc++.h>
#define N 500000
using namespace std;
int n , m , head[N] , tot , path[N] , vis[N] , sta , en , ind[N];
struct edge
{
    int next , to;
} e[N];
inline void add(int x , int y)
{
    e[++tot].next = head[x];
    head[x] = tot;
    e[tot].to = y;
}
queue<int>q;
void bfs(int x)
{
    vis[x] = 1;
    q.push(x);
    path[x] = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].to;
            if(!vis[v])//如果这个点可走 
            {
                int v = e[i].to;
                path[v] = path[u] + 1;//path记录路径长度 
                if(v == sta)
                {
                    cout << path[v];//输出 
                    exit(0);//结束程序 
                }
                vis[v] = 1;//否则染色 
                q.push(v);//入队 
            }

        }
    }
}//这个暴力很简单的呦 
void judge(int x)
{
    for (int i = head[x]; i; i = e[i].next)
    {
        int v = e[i].to;
        vis[v] = 1;
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        int a , b;
        cin >> a >> b;
        add(b , a);
        ind[a]++;//为了搜寻哪一个点的入度为零，就标记一下 
    }
    cin >> sta >> en;
    for (int i = 1; i <= n; i ++)
    {
        if(!ind[i] && i != en)
            judge(i);//judge函数用来把这个点所有连的点染色 
    }
    bfs(en);//开始遍历 
    cout << -1;
}

管理大大求过