题面
给定一张带正权的无向图和一个源点，求边权和最小的最短路径树。
$ n,m \leq 3 \times 10^5 $
感谢 @高飞@Luogu 提供的翻译
题解
什么是最短路径树 （其实CF英文题面中有）:
考虑一个连通无向图 $G$，一个以顶点 $rt$ 为根节点的最短路径树 $T$ 是图 $G$ 满足下列条件的生成树——树 $T$ 中从根节点 $rt$ 到其它顶点 $u$ 的路径距离，在图 $G$ 中是从 $rt$ 到 $u$ 的最短路径距离。
所以，我们可以先求出这个原图中，从源点出发到所有点距离最短是多少，在求的过程中，便可以记录每个被扩展的点的父亲，以建出一个最短路径树。
联系最小生成树的思路，我们可以发现每次扩展点的时候，被扩展到的点的父边只要最小，就能保证最终得到的最短路径树最小。
实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
int to,nxt,w;
}ed[300030*2];int edcnt=1;
int hd[300030];
inline void adde(int u,int v,int w){
ed[++edcnt].to=v;
ed[edcnt].nxt=hd[u];
ed[edcnt].w=w;
hd[u]=edcnt;
}
int n,m;
int vis[300030],p[300030];
ll dis[300030];
priority_queue<pair<ll,int> > pq;
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=m;++i){
scanf("%d%d%d",&u,&v,&w);
adde(u,v,w);adde(v,u,w);
}
int U;
scanf("%d",&U);
pq.push(make_pair(0ll,U));
memset(dis,0x3f,sizeof dis);
dis[U]=0;
while(pq.size()){
int u=pq.top().second;pq.pop();
if(vis[u])continue;
vis[u]=1;
for(int id=hd[u];id;id=ed[id].nxt){
int w=ed[id].w,v=ed[id].to;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
p[v]=id; // 记录扩展的点的父边
pq.push(make_pair(-dis[v],v));
}else if(dis[u]+w==dis[v]&&w<ed[p[v]].w)
p[v]=id; // 如果有 满足到v的距离最短情况下 更短的父边 就修改一下
}
}
ll ans=0;
for(int i=1;i<=n;++i){
if(i==U)continue;
ans+=ed[p[i]].w;
}
printf("%lld\n",ans);
for(int i=1;i<=n;++i){
if(i==U)continue;
printf("%d ",(p[i]>>1));
}
}