最短路径树

日报

一、定义

最短路径树（Shortest Path Tree），简称 SPT，即在一张联通图中，满足从根节点到任意节点的最短路径都为从原图根到任意点的最短路径的树。

二、求法

若只要求出一个最短路径树很简单。

1. 先用最短路算法（一般用 dijkstra）求出从根节点出发的单源最短路；

2. 枚举 $u$，再枚举 $u$ 的相邻节点 $v$，若有 $dis_v = dis_u + w$，则当前连接 $u$ 和 $v$ 的边就在最短路径树里。

三、例题

P5201 [USACO19JAN]Shortcut G

本题只是用到了最短生成树的定义，只要构造一棵字典序最小的最短生成树即可。然后就是根据题目模拟，设连接 $u$ 到 $1$ 的权值为 $T$ 的边，$num_u$ 为以 $u$ 为子树的奶牛个数，那么减少量即为 $num_u \times (dis_u - T)$。

CF545E Paths and Trees

本题不同之处在于要求最短路径树的比权和最小。我们用 $pre_i$ 存 $i$ 之前连的边，然后若有满足条件的取边权最小的即可。

CF1005F Berland and the Shortest Paths

本题和 #10064. 「一本通 3.1 例 1」黑暗城堡，很像，只不过要输出方案，只要用 vector 存一下满足条件的边，然后 dfs 即可。

CF1076D Edge Deletion

建出最短路径树，再输出树上的边即可。