[acwing]第1天

2.1.3 BFS中的双向广搜和A-star：https://www.acwing.com/video/455/

双向广搜就是用两个队列分别从头和从尾开始bfs，每次扩展下一层的时候用size小的扩展，并且是一次扩展一整层(把dis=队头的全部扩展掉)，当两个队列相遇的时候返回（相遇指的是在disa,disb中同时出现某个状态时）

A-star：用优先队列维护，队列里的值是一个pii，pair第一维是 从起点到当前点的真实距离+从当前点到终点的估计距离（用估价函数计算），第二维是保存当前点的状态信息，其他与正常bfs/dijkstra类似，核心就在于通过估价函数使得搜索顺序改变，能够更快地找到最短距离。

注意：A*只能保证求出终点的最短路，这是因为估价函数只是针对于终点涉及的

估价函数：需要满足估价<=真实的最短距离，一般选择理论上的最短距离

例如：八数码问题中：估价函数选择当前这个状态到终点状态的曼哈顿距离（即理论上的最短距离）

　　第K短路中：估价函数选择的是从终点做的一个dijkstra求得的最短路，另外这个问题对于第K短路的处理也很有意思，是通过第K次出队来判断的

整体来说，思路都还是比较套路的，主要题目练习的不多，还不太熟悉，同时码量都不小，为了避免自闭debug，直接抄了一遍，以后在复习的时候再自己练练吧

感觉这种类型的题目几乎不太可能在比赛中遇到或者有机会做出来吧

时间统计：看视频（两倍速）+码代码（只是抄了一下，把思路整理）+记博客：刚好2.5h

ps：为了督促自己学习新算法，开启每日acwing，如果顺利的话，暑假前可以把提高课刷完，然后暑假继续学习进阶课，学习过程中可以顺便看oiwiki，其他的算法学习方式感觉就没必要了，先把acwing搞定再说。

记录方式和cf一样，先把两小时的视频看完，边看边刷题，最后博客总结一下

cf的vp的话，每天就一场ok了，主要是能把vp的补题补完

acw的话，状态好的时候就多学几节吧，尽快把知识框架补齐

说来可笑，打acm打到大二了，很多稍微进阶一点的算法都不会，过去一年可以说基本只是在练习cf思维题，还是1600以下的

每天起来先花4h，把cf的vp和acw的课刷完，后面还想学的话，cf补题或者继续acw的课