【题解】洛谷P2296 [NOIP2014]寻找道路

题目

洛谷P2296寻找道路

题解

如果要确定一个点能否到达终点,就要从这个点开始搜索,想要确定所有的点,很耗时间。于是考虑反向操作,看从终点能倒着访问到哪些点。建一张反图(交换每条边的两个端点),从终点开始搜索,能够到达的点即是可以到终点的点。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月22日 上午9:41

【小白解析】
此题关键在于“倒推”,因此需要两个路线方向完全相反的点数组e1[]与e2[]。
bfs()方法着手实现倒退图的完成。其从终点t出发,反向查询出所有能够到达t的路径,以及该线路上的每一个出发点(具体函数中体现为“终点y”,但由于线路反向,故为出发点)。get_point()随即正向查询每一个能到达上述出发点的x,将能够满足该条件的x在can[]数组上标1。
接下来就是喜闻乐见的dijkstra()。