最短路樹

定義

最短路樹：以圖上一個點為根節點，刪去部分邊後所形成的樹，樹的邊權滿足任意一點與根結點的路徑長度等於圖上兩點的最短路徑長度。

求法

可以採用 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\) 所對應的邊所構成的最短路樹邊權一定最小。