最短路树和最短路 DAG

## 最短路树 最短路树是原图的一棵生成树，通常以起点 $s$ 为根。 对于任意点 $x$，树上 $s$ 到 $x$ 的距离等于 $s$ 到 $x$ 的最短路。 建树：求最短路的过程中，若点 $x$ 最后一次被边 $(x,y)$ 松弛，则保留边 $(x,y)$。 习题：[CF545E Paths and Trees](https://www.luogu.com.cn/problem/CF545E) ## 最短路 DAG 对于任意 $x$，最短路 DAG 中包含所有 $s$ 到 $x$ 最短路经过的边。 性质： 1.最短路 DAG 是有向无环图。若存在环，则原图中存在负环或 0 权环，此时不存在最短路 DAG。 2.最短路 DAG 的每一棵生成树都是最短路树，所有最短路树都是最短路 DAG 的生成树。 建图：求出最短路后，对于边 $(x,y)$，若 $d_x+len_{(x,y)}=d_y$，则保留这条边。 习题： [CF1005F Berland and the Shortest Paths](https://www.luogu.com.cn/problem/CF1005F)（利用性质 2 求出所有所有最短路树） [P2149 [SDOI2009]Elaxia的路线](https://www.luogu.com.cn/problem/solution/P2149)（最短路 DAG 上拓扑求最长链） [CF1163F Indecisive Taxi Fee](https://www.luogu.com.cn/problem/CF1163F)（断边最短路） [题解](https://www.luogu.com.cn/blog/221955/solution-cf1163f)