题解 P2296 【寻找道路】

BCZSX · 2019-07-31 19:18:45 · 题解

好不容易过了这道绿题，这道题卡了我几个月了

先说说思路吧

思路：

用一个vector存下每一条反向边，然后从终点开始bfs，能到达的点就用一个flag数组打个标记，这样便于之后搜索……

然后清空vector，将正向边存进去（注意要使用数组存边，这样才能正反存2次）……

接着我们查看每个点的出边所指向的点是否能到达终点，如果有一个达不到，用check数组标记（注意不能直接修改，会有后效性）

最后跑一遍dijkstra就好了，注意有输出-1的情况

上代码了

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define MAXN 10100
#define MAXM 201000
#define INF 0x3f3f3f3f

queue<int> que;//搜索用的队列
vector<int> vec[MAXN];//存边用的vector
int n, m, s, t;//题目所述
int x[MAXM], y[MAXM], dis[MAXN];//存边和dijkstra的数组
bool flag[MAXN], vis[MAXN], check[MAXN];//刚才讲过了，vis数组标记是否遍历过

void pre()//预处理每个点是否能到达终点
{
    que.push(t);
    vis[t] = flag[t] = 1;
    while (! que.empty())
    {
        int x = que.front();
        que.pop();
        for (int i = 0; i < vec[x].size(); ++ i)
        {
            int v = vec[x][i];
            if (vis[v])
                continue;
            flag[v] = vis[v] = 1;
            que.push(v);
        }
    }
    for (int i = 1; i <= n; ++ i)
        vec[i].clear();
    for (int i = 1; i <= m; ++ i)
        vec[x[i]].push_back(y[i]);
    for (int i = 1; i <= n; ++ i)//查看每个点出边指向的点能否到达终点
        for (int j = 0; j < vec[i].size(); ++ j)
            if (! flag[vec[i][j]])
            {
                check[i] = true;
                break;
            }
    for (int i = 1; i <= n; ++ i)
        flag[i] = (! check[i]);//标记
}

int bfs()
{
    memset(vis, 0, sizeof(vis));//注意再次搜索要清0
    for (int i = 1; i <= n; ++ i)
        dis[i] = INF;
    dis[s] = 0;
    vis[s] = 1;
    que.push(s);
    while (! que.empty())
    {
        int x = que.front();
        que.pop();
        vis[x] = false;
        for (int i = 0; i < vec[x].size(); ++ i)
        {
            int v = vec[x][i];
            if (dis[v] > dis[x] + 1 && flag[v])
            {
                dis[v] = dis[x] + 1;
                if (! vis[v])
                    que.push(v), vis[v] = 1;
            }
        }
    }
    return dis[t] == INF ? -1 : dis[t];//输出答案
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++ i)//建反向边
    {
        scanf("%d%d", &x[i], &y[i]);
        if (x[i] == y[i])
            -- i, -- m;
        vec[y[i]].push_back(x[i]);
    }
    scanf("%d%d", &s, &t);
    pre();//预处理
    printf("%d", bfs());//输出
    return 0;
}