首页 > 代码库 > 未解决之图论寻路问题

未解决之图论寻路问题

2024-09-01 12:00:44   217人阅读

有时候我们想找到v节点之后。。回溯更新答案。。而其他不在路径上的点我们不关心。。注意这种路径可能有很多条。。

不可能每次都回溯到起点，我的想法是回溯到起点再统计答案来着，目前来看好像不太行

如果到终点再统计答案的话。。我的一贯做法是dfs参数增加深度关键字。。这样不一样的转折节点同深度的可以刷掉，到终点以后可以方便统计答案

for{if(v==t) return ?}

有时候想找到一条可行路径就返回 我的办法是for里面加一个全局的bool..,找到就是false,退出

对于老生重现赛1，D

qls的另外一个高级做法。。

 开一棵线段树，每个节点维护把这个区间内的边加进并查集之后的状态
合并两个区间只需要 O(n) bfs 一下
那么对于一次查询
枚举左端点然后线段树上二分右端点
==
当有两个不确定因素时。。我们可以枚举一端。。然后二分另外一端。。
==
然后我对于dij有了新的认识。。虽然说当前选了最短的路。。不一定保证s-t最短。。
但是你在算d[t]的时候考虑了所有之前所有最短路程的父亲。。可以说是用到了dp的思想。。
用类似于枚举的方法将不确定性去掉。。
初始化为无穷大这个trick也是非常非常的精髓。。
可以说dij就凭这一个算法在我心中已经是大师了。。
可以说一旦你固定了终点。。对于终点的前一个点来说。。一定是w+dis[pre]越小越好。。w是变化的，dis[pre]也是变化的。。一定要好好体会
然后对于它的父亲们来说。。w不变。。dis越小越好。。
=====
 

未解决之图论寻路问题


联系
我们