LuoGuP2296寻找道路
简化题意 $:$
要求从 $1$ 号点到 $n$ 号点的最短路,不能走障碍点.
一个点不是障碍当且仅当它的所有出边指向的点能到达终点.
如何去判断一个点是否是障碍点呢 $?$
很简单,我们先做一遍逆拓扑(也就是在反图上以终点为起点做 $bfs$),处理出哪些点能与终点连通.
枚举每个点,遍历其所有出边指向的点,如果存在一个点与终点不连通,就把当前点标记为障碍.
最后再正向做一遍 $bfs$ 即可.
1 |
|
My Coding Life.
简化题意 $:$
要求从 $1$ 号点到 $n$ 号点的最短路,不能走障碍点.
一个点不是障碍当且仅当它的所有出边指向的点能到达终点.
如何去判断一个点是否是障碍点呢 $?$
很简单,我们先做一遍逆拓扑(也就是在反图上以终点为起点做 $bfs$),处理出哪些点能与终点连通.
枚举每个点,遍历其所有出边指向的点,如果存在一个点与终点不连通,就把当前点标记为障碍.
最后再正向做一遍 $bfs$ 即可.
1 | #include <algorithm> |