最短路径树，即Shortest Path Tree，对于一张无向图，固定一个源点，树上每个点到源点的最短距离都等于原图中该点到源点的最短距离。
最短路径树是所有路径树中边权和最小的。
通常使用dijkstra算法来找出SPT，在每次松弛操作时，如果松弛成功，记该点的前驱边的编号，因为边时逐一加进堆中的，所以最后形成的是一棵SPT。
注意，松弛操作需要判断相等，相等时也算松弛成功。
假设两条路径到y的dis相等，分别有x1->y和x2->y，若dis[x1]<dis[x2]，可以知道(x1->y)>(x2->y)，同时在dijkstra中x1先于x2被扩展到，取后者x2更优。
void dijkstra(int s){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
q.push({0,s});
while(!q.empty()){
int x=q.top().second;
q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(dis[y]>=dis[x]+e[i].w){
dis[y]=dis[x]+e[i].w;
q.push({dis[y],y});
pre[y]=i;
}
}
}
}
给定无向图的源点，求边权和最小的最短路径树。记录每个点的前驱边后，对前驱边的权值进行累加。
cin>>s;
dijkstra(s);
for(int i=1;i<=n;i++){
if(i==s)continue;
sum+=e[pre[i]].w;
}
cout<<sum<<'\n';
for(int i=1;i<=n;i++)if(i!=s)cout<<(pre[i]+1>>1)<<' ';
给定无向图，要求删边至最多剩余k条边，定义好点为最后1点到它的最短路长度仍然等于原图中的最短路长度的节点，最大化好点的个数。将保留的边建成一棵树，即在原图中选出min(k,n-1)条边，在dijkstra后判断从1开始dfs，判断每条边是否在SPT上并记录数量即可。
void dfs(int x){
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(i==pre[y]){
cout<<(i+1>>1)<<' ';
dfs(y);
}
}
}
给定无向图，选n-1条道路，使得1到所有城市的距离和最小，准备k个可能方案，若方案数少于k种则输出方案。由于边权均为1，可以使用bfs跑最短路，在每个点被松弛时，将该点的前驱边存入该点的集合，最后的方案数就是每个点集合大小的乘积。由于当dis[y]>dis[x]+1时，y一定是首次被扩展到，集合中没有元素，所以不需要清空集合。
inline void bfs(int s){
queue<int>q;
memset(dis,0x3f,sizeof(dis));
q.emplace(s);
dis[s]=0;
while(!q.empty()){
int x=q.front();
q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(dis[y]>=dis[x]+1){
dis[y]=dis[x]+1;
v[y].emplace_back(i+1>>1);
q.emplace(y);
}
}
}
}
void dfs(int dep){
if(dep==n+1){
for(int i=1;i<=m;i++)cout<<vis[i];
if(++num>=k)exit(0);
cout<<'\n';
return;
}
for(auto x:v[dep]){
vis[x]=1;
dfs(dep+1);
vis[x]=0;
}
}
bfs(1);
int cnt=1;
for(int i=2;i<=n;i++){
if(cnt*v[i].size()>k){
cnt=k;
break;
}
else cnt*=v[i].size();
}
cout<<cnt<<'\n';
memset(vis,0,sizeof(vis));
dfs(2);