NOIP2014 寻找道路题解
riteme.site

[NOIP2014] 寻找道路

原题题意

给你一张$ n(n \le 1000) $个点和$ m(m\le200000) $条边权为1的无向边的图,找出一条符合下列要求的路径:
1. 路径上的所有点的出边所指向的点都直接或间接与终点连通。
2. 在满足条件 1 的情况下使路径最短。

做法

既然路径上的所有点都要满足要求1,于是我们先求出这张有向图中哪些点满足要求。
我们使用一个valid数组来存储某个点是否直接或间接地到终点的布尔值,故最暴力的方法就是每个点DFS。其实只需要一次DFS即可,因为只要任意一个与某个点的出边相连接的点能够到达终点,那么这个点也可以到达终点,否则不行。这样在写的过程中,比较麻烦,因此我们在读入图的时候同时构造一张反向图,即每条边与原图方向相反,然后从终点BFS,将每个可以便利到的点打上标记。
做完这个处理后,只需要从起点BFS就能求出答案。