XiaoHuang's Space
XiaoHuang's Space
XiaoHuang
May the force be with you.
『题解』洛谷P2296 寻找道路
Posted: Dec 11, 2019
Last Modified: Dec 13, 2019
This article was last modified days ago. The content of this post may be outdated!

Portal

Portal1: Luogu

Portal2: LibreOJ

Description

在有向图$\mathrm G$中,每条边的长度均为$1$,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:

  1. 路径上的所有点的出边所指向的点都直接或间接与终点连通。

  2. 在满足条件$1$的情况下使路径最短。
    注意:图$\mathrm G$中可能存在重边和自环,题目保证终点没有出边。 请你输出符合条件的路径的长度。

Input

第一行有两个用一个空格隔开的整数$n$和$m$,表示图有$n$个点和$m$条边。

接下来的$m$行每行$2$个整数$x, y$,之间用一个空格隔开,表示有一条边从点$x$指向点$y$。

最后一行有两个用一个空格隔开的整数$s, t$,表示起点为$s$,终点为$t$。

Output

输出只有一行,包含一个整数,表示满足题目描述的最短路径的长度。

如果这样的路径不存在,输出$-1$。

Sample Input1

3 2
1 2
2 1
1 3

Sample Output1

-1

Sample Input2

6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5

Sample Output2

3

Solution

我们先看一个例子:

不妨令起点为$1$,终点为$3$。

这个例子的答案是$3$,路径是$1 \to 4 \to 5 \to 3$。

我们可以先检验出每一个点是否能到终点。可以从终点出发,按照反向边走一遍,然后把走不到的点以及它的入边连的点都删除,像这样:

最后在跑一边$bfs$序,求出最短路就可以了。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

const int MAXN = 200005;
struct EDGE {
    int to, nxt;
} edge1[MAXN], edge2[MAXN];
int n, m, u, v, S, T, cnt1, cnt2, dis[MAXN], head1[MAXN], head2[MAXN];
bool vis[MAXN];
inline void addedge(int u, int v) {//邻接表存图
    edge1[++cnt1].to = v; edge1[cnt1].nxt = head1[u]; head1[u] = cnt1;
    edge2[++cnt2].to = u; edge2[cnt2].nxt = head2[v]; head2[v] = cnt2;//反向边
}
inline void bfs1(int cur) {
    queue<int> Q;
    Q.push(cur);
    vis[cur] = 1;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int i = head2[u]; ~i; i = edge2[i].nxt) {//遍历每一个点
            int v = edge2[i].to;
            if (!vis[v]) {
                vis[v] = 1;
                Q.push(v);
            }
        }
    }
}
inline bool check(int u) {//判断是否能到达终点
    for (int i = head1[u]; ~i; i = edge1[i].nxt)
        if (!vis[edge1[i].to]) return 0;
    return 1;
}
inline bool bfs2(int cur) {
    queue<int> Q;
    Q.push(cur);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        if (!check(u)) continue;
        for (int i = head1[u]; ~i; i = edge1[i].nxt) {//遍历每一个点
            int v = edge1[i].to;
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                Q.push(v);
                if (v == T) {
                    printf("%d\n", dis[T] + 1);
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main() {
    scanf("%d%d", &n, &m);
    memset(head1, -1, sizeof(head1));
    memset(head2, -1, sizeof(head2));
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        addedge(u, v);//加边
    }
    scanf("%d%d", &S, &T);
    bfs1(T);//求出终点能到的点
    memset(dis, -1, sizeof(dis));
    if (!bfs2(S)) printf("-1\n");
    return 0;
}

Attachment

测试数据下载:https://www.lanzous.com/i5qa0pg

Article License: CC BY-NC-ND 4.0
Article Author: XiaoHuang
  1. 1. Portal
  2. 2. Description
  3. 3. Input
  4. 4. Output
  5. 5. Sample Input1
  6. 6. Sample Output1
  7. 7. Sample Input2
  8. 8. Sample Output2
  9. 9. Solution
  10. 10. Code
  11. 11. Attachment
Newer Post
『题解』洛谷P3958 奶酪
Older Post
『题解』洛谷P2170 选学霸
Buy me a beer?
-->
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×