E - Road Reduction

E - Road Reduction (atcoder.jp)

题意:一棵树n个点，m条路， di表示1-i的距离，问怎么选择边可以使得d2+...dn最短。

题解: 很明显，就是直接套最短路板子，判断每一个点的最短路，题目里没有负权值，直接dijkstra就可以了。边如何记录，与每个点相连的那个最短路的边，每次更新出来储存，然后直接输出即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pll;

const int N=5e5+5;

ll vis[N],pre[N];

ll dis[N],cnt,head[N];

ll ans[N];

struct ss{

  ll next,to,w,id;

}e[N];

void add(ll x,ll y,ll w,ll id){

  e[++cnt].to=y;

  e[cnt].w=w;

  e[cnt].id=id;

  e[cnt].next=head[x];

  head[x]=cnt;

}

void dij(){

   priority_queue<pll,vector<pll>,greater<pll> >q;

   memset(dis,0x3f,sizeof(dis));

   memset(vis,0,sizeof(vis));

   q.push({0,1});

   dis[1]=0;

   while(!q.empty()){

     ll v=q.top().first;

     ll u=q.top().second;

     q.pop();

     if(vis[u]) continue;

     vis[u]=1;

     for(ll i=head[u];i;i=e[i].next){

       ll j=e[i].to;

       if(dis[j]>v+e[i].w){

         dis[j]=dis[u]+e[i].w;

         q.push({dis[j],j});

         ans[j]=e[i].id;

       }

     }

   }

}

signed main(){

  ios::sync_with_stdio(false);

  cin.tie(0);

  ll n,m;cin>>n>>m;

  for(ll i=1;i<=m;i++){

    ll x,y,w;cin>>x>>y>>w;

    add(x,y,w,i);

    add(y,x,w,i);

  }

  dij();

  for(int i=2;i<=n;i++){

    cout<<ans[i]<<" ";

  }

} 

E - Road Reduction的相关教程结束。