前置知识：
1: 单源最短路径算法
何为最短路径树？
所谓最短路径树 (Shortest Path Tree) ，简称 SPT ，就是从一张连通图中，有树满足从根节点到任意点的路径都为原图中根到任意点的最短路径的树。
可能描述的有点繁琐，如果看不懂可以观看一下百度百科给出的定义：
考虑一个连通无向图 G ，一个以顶点 v 为根节点的最短路径树 T 是图 G ，满足下列条件的生成树——树 T 中从根节点 v 到其它顶点 u 的路径距离，在图 G 中是从 v 到 u 的最短路径距离。
1 最短路径树是一棵生成树，保证每一个点联通。
2 从根节点在这棵树上的任意点路径 = 原图两点之间的最短路径，即任意点 i 都有 len_i = dis_i。
最短路径树×最小生成树的区别？
最小生成树只是满足全图联通且边权集最小，而最短路径树是满足从根节点到任意点的最短路。
更直观的显示如下：
原图：
最短路径树：
最小生成树：
最短路径树的边权和为 75 ，最小生成树的边权和为 67 。
另外的，最短路径树的边权和 ≥ 最小生成树的边权和。
如何得出最短路径树？
根据定义，最短路径树是从根节点到任一点的路径都为最短路，由此我们可以想到单源最短路径算法，常用的单源最短路径算法有 Dijkstra 和 Bellman-Ford ，这里我们使用 Dijkstra 。
代码如下：
```cpp
void Dijskra(int start) { // 源点
priority_queue <Node> pq; // 优先队列维护当前全职最小
for(register int i = 1; i <= n; ++i) {
dis[i] = INF; // DP初始化
}
dis[start] = 0; // DP的边界条件
node Start = {start, 0};
pq.push(Start); // 确定源点到源点的最短路径 将源点放入优先队列进行广搜
while(!pq.empty()) {
node u = pq.top(); // 中转点
pq.pop();
int x = u.id, w = u.dist;
if(vis[u]) {
continue; // 防止多次将一个点加入堆中
}
vis[u] = true;
for(register int i = head[u]; i; i = edges[i].next) { // 找邻居
int next = edges[i].to, w = edges[i].w;
if(dis[next] - dis[u] > w) { // 松弛操作
dis[next] = dis[u] + w;
Node nxt = {next, dis[next]};
pq.push(nxt);
}
}
}
return ;
}
```
我们在进行该算法，对于每一个节点都是由一条边拉进来的，当前存入 $dis$ 这个集合，每次进行松弛的时候都会将一个**新点**拉入集合，这样从根节点 $($ 源点 $)$ 可以形成树。因为在树中**一个点就可以对应一条边**，我们可以使用一个数组 $pre$ 来记录点 $i$ 的**前驱**，即从源点到点 $i$ 的**上一条边的编号**。
Tip: 这里 $pre$ 记录是**边的编号**而不是点的编号。
而很多时候，我们需要保证树上所有的**边权和最小**，所以我们可以采用一个**贪心**的思想，进行松弛的时候如果**松弛前的结果**与**松弛后的结果**相等即 $dis[now] = dis[next] + w$，我们可以比较两种情况时，**连接这条点的边的大小**，即 $w[i]$ 与 $w[pre[next]]$ ，如果$w[i] < w[pre[next]]$ ，那么我们更新当前的 $pre$ 。
```cpp
for(register int i = head[u]; i != 0; i = edges[i].next) { // 找邻居
int next = edges[i].to, w = edges[i].w;
if(dis[next] - dis[u] > w) { // 松弛操作
dis[next] = dis[u] + w;
Node nxt = {next, dis[next]};
pq.push(nxt);
pre[next] = i;
}
if(dis[next] == dis[u] + edges[i].w && edges[i].w < edges[pre[next]].w) { // 松弛前后相等，比较前驱
pre[next] = i;
}
}
```
## 如何应用？
[CF545E Paths and Trees](https://www.luogu.com.cn/problem/CF545E)
### 题意：
给定一张带边权的联通无向图 $G$ ，有 $n(1≤n≤300000)$ 个点和 $m$ 条边，再给定一个顶点 $u$ ，求此图中**边权和最小**的 $SPT$ ，输出该树权值和和和每条**边的编号**。
### 分析：
如果我们一开始没有接触过**最短路径树**，那么对于这道题我们很容易想到**最小生成树**，而这种方法上面已经说明是错的。
不考虑正解的前提下，我们还有一种**暴力**的方法，使用 $Dijkstra$ 找出权值和最小的最短路径树的**权值和**，然后再暴力枚举，选一条边，**如果把这条边删掉，对最小花费有影响，说明这个肯定是最短路径树上的边**，此算法权值和为 $O((n \log_2 n)^2)$ 。
**正解**前文已上述，由于答案还要输出构成该树的边的编号，由于我们采用**链式前向星**建的双向边，所以原题中所有边的编号都存了两次，根据 $int$ 除法**向下取整**的特性，我们只需对编号 $pre + 1$ $/2$。
综上，时间复杂度为 $O((n + m) \log_2 n)$ 。
### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while(c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int Maxn = 3e5 + 5;
const int Maxm = 6e5 + 5;
int n, m, s, cnt = 0, head[Maxn], pre[Maxn];
long long dis[Maxn], ans[Maxn];
bool vis[Maxn];
struct Line { // to指向的点， w是边权， next是这一条边连接的下一条边是谁
int to;
int w;
long long next;
} edges[Maxm]; // 存所有的边
inline void Add(int a, int b, long long w) { // 添加边的函数
++cnt; // 边的编号
edges[cnt].to = b; // 第cnt条边指向点y
edges[cnt].w = w; // 第cnt条边的权值
edges[cnt].next = head[a]; // 第cnt条边的指向连接点x的第一条边
head[a] = cnt; // 将连接点x的第一条边更新为第cnt条边
return ;
}
struct Node {
int id;
long long dist;
bool operator < (const Node &cur) const {
return dist > cur.dist;
}
} ;
inline void Dijkstra(int start) {
priority_queue <Node> pq; // 优先队列维护当前权值最小
for(register int i = 1; i <= n; ++i) {
dis[i] = INF; // DP初始化
vis[i] = false;
}
dis[start] = 0; // DP的边界条件
Node Start = {s, 0};
pq.push(Start); // 确定源点到源点的最短路径 将源点放入优先队列进行广搜
while(!pq.empty()) {
Node now = pq.top();
pq.pop();
int u = now.id; // 中转点
if(vis[u] == true) {
continue; // 防止多次将一个点加入堆中
}
vis[u] = true;
for(register int i = head[u]; i != 0; i = edges[i].next) { // 找邻居
int next = edges[i].to;
long long w = edges[i].w;
if(dis[next] > dis[u] + w) { // 松弛操作
dis[next] = dis[u] + w;
Node nxt = {next, dis[next]};
pq.push(nxt);
pre[next] = i;
}
if(dis[next] == dis[u] + edges[i].w && edges[i].w < edges[pre[next]].w) {
pre[next] = i;
}
}
}
return ;
}
signed main() {
n = read(), m = read();
for(register int i = 1; i <= m; ++i) { // m条边
int x = read(), y = read();
long long w = read();
Add(x, y, w), Add(y, x, w); // 双向边
}
s = read();
Dijkstra(s);
long long sum = 0, tot = 0;
for(register int i = 1; i <= n; ++i) {
if(i == s) {
continue; // 源点到自己无边
}
int id = pre[i];
long long w = edges[id].w;
sum += w;
ans[++tot] = id; // 记录边的编号
}
sort(ans + 1, ans + tot + 1);
printf("%lld\n", sum);
for(register int i = 1; i <= tot; ++i) { // 向下取整
printf("%lld ", (ans[i] + 1) / 2);
}
puts("");
return 0;
}
```
[CF1076D Edge Deletion](https://www.luogu.com.cn/problem/CF1076D)
### 题意：
给定一个 $n(1≤n≤300000)$ 个点,$m(1≤m≤300000)$条边的无向简单带权连通图, 要求删边至最多剩余 $k$ 条边。
定义**好点**是指删边后, 1号节点到它的最短路长度仍然等于原图最短路长度的节点。
最大化删边后的好点个数。
### 分析：
通过上述知识，我们可以发现好点的定义就是**最短路径树**上的点，所以我们只需要将1号节点当做根节点，使用 $DFS$ 从其出发进行遍历 $min(n, k + 1)$ 个节点，就可以保证图**联通**了。
### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long // 坏习惯...
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while(c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int Maxn = 3e5 + 5;
const int Maxm = 6e5 + 5;
int n, m, s, k, cnt, sum, head[Maxn], dis[Maxn], pre[Maxn];
bool vis[Maxn], ins[Maxm];
struct Line {
int to;
int w;
int next;
} edges[Maxm];
inline void Add(int a, int b, int w) {
++cnt;
edges[cnt].to = b;
edges[cnt].w = w;
edges[cnt].next = head[a];
head[a] = cnt;
return ;
}
struct Node {
int id;
int dist;
inline bool operator < (const Node &cur) const {
return dist > cur.dist;
}
} ;
void Dijkstra(int start) {
priority_queue <Node> pq;
for(register int i = 1; i <= n; ++i) {
dis[i] = INF;
vis[i] = false;
}
dis[start] = 0;
Node Start = {start, 0};
pq.push(Start);
while(!pq.empty()) {
Node now = pq.top();
pq.pop();
int u = now.id;
if(vis[u] == true) {
continue;
}
vis[u] = true;
for(register int i = head[u]; i != 0; i = edges[i].next) {
int next = edges[i].to, w = edges[i].w;
if(dis[next] - dis[u] > w) {
dis[next] = dis[u] + w;
Node nxt = {next, dis[next]};
pq.push(nxt);
pre[next] = i;
}
if(dis[next] == dis[u] + edges[i].w && edges[i].w < edges[pre[next]].w) {
pre[next] = i;
}
}
}
for(register int i = 1; i <= n; ++i) {
vis[i] = false;
}
return ;
}
void DFS(int x, int father) {
if(sum == k) {
puts("");
exit(0);
}
for(register int i = head[x]; i != 0; i = edges[i].next) {
int next = edges[i].to, w = edges[i].w;
if(next == father) {
continue;
}
if(pre[next] == i) {
++sum;
vis[next] = true;
printf("%d ", (i + 1) / 2);
DFS(next, x);
}
}
return ;
}
signed main() {
n = read(), m = read(), k = read();
for(register int i = 1; i <= m; ++i) {
int a = read(), b = read(), w = read();
Add(a, b, w), Add(b, a, w);
}
Dijkstra(1);
printf("%lld\n", min(n - 1, k));
DFS(1, 0); // 遍历节点，建树输出
return 0;
}
```
[CF1005F Berland and the Shortest Paths](https://www.luogu.com.cn/problem/CF1005F)
### 题意：
给定一个 $n(1≤n≤200000)$ 个点,$m(1≤m≤200000)$条边的无向简单连通图，每条边权为 $1$ ，求最短路径树的方案数，并输出每种方案
### 分析：
通过上述知识，我们可以知道这是个最短路计数问题，由于每个边的边权为 $1$ ，所以我们求最短路径树的时候可以要将**最短路退化成广搜**。
对于方案，我们可以在加边记录边的编号，然后对每个点维护一个能转移其的最短路的边的**编号集**，这样总的方案数就是**所有集合大小的乘积**，然后用 $DFS$ 在每个集合中选一个元素输出。
### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while(c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int Maxn = 3e5 + 5;
const int Maxm = 6e5 + 5;
int n, m, s, k, cnt, sum, tot = 1, head[Maxn], dis[Maxn], pre[Maxn];
bool vis[Maxn];
struct Line {
int to;
int next;
int num;
} edges[Maxm];
inline void Add(int a, int b, int w) {
++cnt;
edges[cnt].to = b;
edges[cnt].next = head[a];
edges[cnt].num = w;
head[a] = cnt;
return ;
}
vector <int> v[Maxn];
void BFS(int start) {
queue <int> q;
q.push(start);
dis[start] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(register int i = head[u]; i != 0; i = edges[i].next) {
int next = edges[i].to, num = edges[i].num;
if(!dis[next]) {
dis[next] = dis[u] + 1;
v[next].push_back(num);
q.push(next);
} else if(dis[next] == dis[u] + 1) {
v[next].push_back(num);
}
}
}
return ;
}
void DFS(int x) {
if(x == n + 1) {
for(register int i = 1; i <= m; ++i) {
printf("%d", vis[i]);
}
puts("");
sum++;
if(sum == tot) {
exit(0);
}
return ;
}
for(register int i = 0; i < v[x].size(); ++i) {
vis[v[x][i]] = 1;
DFS(x + 1);
vis[v[x][i]] = 0;
}
return ;
}
signed main() {
n = read(), m = read(), k = read();
for(register int i = 1; i <= m; ++i) {
int x = read(), y = read();
Add(x, y, i), Add(y, x, i);
}
BFS(1);
for(register int i = 2; i <= n; ++i) {
if(tot * v[i].size() > k) {
tot = k;
break;
} else {
tot *= v[i].size();
}
}
printf("%d\n", tot);
DFS(2);
return 0;
}
```
## 总结：
1：最短路径树与最小生成树算法 $Kruskal$ 和 $Prim$ 无关。
2：最短路径树是采用**单源最短路径算法**来实现的。
3：注意记录该算法**点与边**的关系。
向先知先觉的 $Dijkstra$ 老爷子致敬！
