简介
= =
大概就是在求完单源最短路之后，对与原图所有边 $(u,v,w)$ 都满足 $dis[v] = dis[u] + w$ 的边所连成的 $DAG$
如果存在 $0$ 边的话则可能不是 $DAG$
一般用的比较多的是最短路径树，需要注意的是我们求得的这棵树的边是有向的
例题
简要题意：给定一个 $n$ 个点 $m$ 条正权边的无向图和一个源点 $s$，求边权和最小的最短路径树
$n,m\le 3\times 10^5$
简要题解：需要注意的是我们不能将最短路径图求出来之后跑 $kruskal$，最短路径图的边是有向的
我们直接贪心对于每个点拿最短的边即可，注意这样一定有解