最短路树

定义

最短路树：以图上一个点为根节点，删去部分边后所形成的树，树的边权满足任意一点与根结点的路径长度等于图上两点的最短路径长度。

求法

可以采用 dij 求解。
每次更新 \(dis_v\) 时，记录每个点最后一次用来更新的边，即为最短路树。

核心代码如下，时间复杂度为 dij 的时间复杂度即 \(m\log m\) 或 \(n^2\)。

for(int i=head[u];i;i=nxt[i]){
	int v = to[i];
	int w = val[i];
	if(dis[v] > dis[u] + w){
		dis[v] = dis[u] + w;
		pre[v] = i;
	}
}

例题

CF545E

本题要求最短路树的总边权最小，只需做如下修改：

if(dis[v] >= dis[u] + w){
	dis[v] = dis[u] + w;
	pre[v] = i;
}

证明如下：
对于每个点 \(v\) 满足最短路树性质时 \(dis_v\) 已经达到最小时，我们发现此时可能还有几条路径可能将其更新为该最小的 \(dis_v\)。

根据堆优化 dij 的性质，先更新的 \(dis_v\) 一定较小，但是又因为 \(dis_u = dis_v + w_{u,v}\)，所以当 \(dis_v\) 最大时，\(w_{u,v}\) 最小。

所以我们选取最晚更新的 \(dis_v\) 所对应的边所构成的最短路树边权一定最小。