[NOIP2014] 寻找道路

原题题意

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

做法

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