[ABC252E] Road Reduction 题解

FFTotoro · 2022-10-22 22:01:19 · 题解

Upd：题解通道重新开放，重新递交审核。

可以由从起点为 1 开始使用 Dijkstra 算法求最短路，就可以算出 d_i。

根据 Dijkstra 的更新情况，每个点都会被至少松弛一次，最后被松弛的那次对应一条边，而 1 是起点，不会被其他边松弛，这样 n-1 个点正好对应 n-1 条边。问题就得到了解决。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
main(){
  ios::sync_with_stdio(false);
  int n,m; cin>>n>>m;
  vector<vector<pii> > g(n);
  vector<int> w(m),p(n),d(n,1e18);
  for(int i=0;i<m;i++){
    int a,b; cin>>a>>b>>w[i];
    g[a-1].emplace_back(b-1,i);
    g[b-1].emplace_back(a-1,i);
  }
  priority_queue<pii,vector<pii>,greater<> >q;
  q.emplace(d[0]=0,0);
  while(!q.empty()){
    auto [f,e]=q.top(); q.pop();
    if(f>d[e])continue;
    if(e)cout<<p[e]+1<<' ';
    for(auto [v,i]:g[e]){
      if(d[e]+w[i]>=d[v])continue;
      p[v]=i; q.emplace(d[v]=d[e]+w[i],v);
    }
  } // Dijkstra
  return 0;
}