概述
原图的一棵生成树，满足每个点到源点的最短路长度等于生成树中每个点到根节点的距离。
在 dij 过程中找每个点的前驱即可。
将所有满足 $dis_v=dis_u+w$ 的边 $(u \to v)$ 加入，得到最短路 DAG，最短路 DAG 的生成树为最短路树。
例题
-
直接贪心。
Berland and the Shortest Paths
每个点是独立的。
Indecisive Taxi Fee（删边最短路）
求出一条 $1 \to n$ 的最短路，记为 $P$，$T_1,T_n$ 表示以 $1,n$ 为源点的最短路树。若 $e \notin P$，那么最短路不变。否则最短路形如 $(1 \to u) + (u \to v) + (v \to n)$。
枚举每条边作为非最短路树上的边，其对 $P$ 的一段区间有贡献，离线扫描线即可。