一、单元最短路模板

1.热浪

https://www.acwing.com/problem/content/1131/

spfa或dijkstra模板

2.信使

https://www.acwing.com/problem/content/1130/

floyd偷懒求法

3.昂贵的聘礼

https://www.acwing.com/activity/content/problem/content/1498/1/

模板套一个应用题。遇到这种描述长的题目不要慌，仔细分析不会很难的。

4.最优乘车

https://www.acwing.com/problem/content/description/922/

最短路不一定是路径长度，也可能是题目中的其它变量，如本题中的换乘次数。

5.最短路计数，（难度更大一点的）观光

https://www.acwing.com/problem/content/description/1136/

https://www.acwing.com/problem/content/385/

最短路和次短路的计数方式

6.bfs,dfs和双端队列bfs求最短路

当边权为固定值的时候，可以用bfs或者dfs，当边权只有两种的时候，可以用双端队列bfs。具体证明从两段性和单调性方面证明（证明略）。

算法名称	能否处理负权边	时间复杂度
dijkstra	不能	O(n^2)
heap-dijkstra	不能	O(mlogn)
bellman-ford	能	O(nm)
spfa	能	O(km)~O(nm)

 

二、建图及搜索方式的变体

1.香甜的黄油

https://www.acwing.com/problem/content/description/1129/

枚举结合单元最短路求最优化问题

2.最优贸易

https://www.acwing.com/problem/content/343/

双向枚举结合单元最短路求最优化问题。通常需要建反边。

3.新年好

https://www.acwing.com/problem/content/1137/

dfs方式枚举结合单元最短路求最优化问题。

4.拯救大兵瑞恩

https://www.acwing.com/problem/content/1133/

分层图+二进制状态压缩

三、综合性的解题技巧

1.通信线路

https://www.acwing.com/problem/content/description/342/

与二分答案相结合

2.道路与航线

https://www.acwing.com/problem/content/344/

当出现负权边，用spfa又超时或被卡的时候，挖掘题目中的限制条件，得出可以用toposort处理负权边。（因为题目肯定是要能做的，所以遇到困难的时候多看看题中有没有特殊性质）