题解 CF545E 【Paths and Trees】

### Preface 最短路径树 (SPT) 模板题。看[洛谷日报](https://xyzl.blog.luogu.org/Shortest-Path-Tree-SPT)发现这玩意儿其实并不难学。 ### Solution 在 dijkstra 求最短路的时候，每次对 $u\to v$ 松弛的时候，都更新 $u\to v$ 所选取的边的编号，即 $pre_v$。由于题目要求最小 SPT，因此松弛的条件要取等号，并更新更小的边。 题解区貌似没有比较简单的 `vector` 实现代码。链式前向星固然方便，不过对于 `vector` 党只需多开一个结构体存边，记录编号即可。 ### Code ```cpp typedef const int cint; typedef long long ll; cint MAXN=3e5+5; int n,m,s; struct node { int to;ll val;int id;//id 即编号 bool operator<(const node& a)const { return val>a.val; } }; struct Edge { int u,v,w; }e[MAXN];//记录边的编号 vector<node> edge[MAXN]; bool visit[MAXN]; ll dis[MAXN]; int pre[MAXN]; void dijkstra(void) { #define pli pair<ll,int> for(int i=1;i<=n;i++) dis[i]=LLONG_MAX; priority_queue<pli,vector<pli>,greater<pli>> q; q.emplace(make_pair(dis[s]=0,s)); while(!q.empty()) { const int u=q.top().second; q.pop(); if(visit[u]) continue; visit[u]=true; for(const auto& cur:edge[u]) { cint v=cur.to;const ll w=cur.val; if(dis[v]>=dis[u]+w) { if(dis[v]>dis[u]+w || e[pre[v]].w>w) pre[v]=cur.id;//核心 dis[v]=dis[u]+w; q.emplace(make_pair(dis[v],v)); } } } } int main() { read(n,m); for(int i=1;i<=m;i++) { int u,v,w;read(u,v,w); e[i]=Edge{u,v,w}; edge[u].emplace_back(node{v,w,i}); edge[v].emplace_back(node{u,w,i}); } read(s); dijkstra(); ll sum=0; vector<int> ans; for(int i=1;i<=n;i++) { if(i==s) continue; sum+=e[pre[i]].w; ans.emplace_back(pre[i]); } sort(ans.begin(),ans.end()); cout<<sum<<endl; for(const auto& Ans:ans) cout<<Ans<<' '; cout<<endl; return 0; } ```