题面。
要求所有点到关键点的距离和最小。
首先要确定这个点去哪个关键点最短。
树上两点间路径与距离是唯一的,所以
我们从两个关键点分别跑dfs。
第一遍求出每个点到s的最短距离。
然后再从t点出发,如果这个点到t点的距离更短,那么这个点就应该去t点。
定向的工作也可以在dfs的时候做。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; #define ll long long const int h=600010; int head[h],last[h],to[h],tot=1; ll len[h]; void add_edge(int x,int y,ll w){ tot++; last[tot]=head[x]; head[x]=tot; to[tot]=y; len[tot]=w; } void add(int x,int y,ll w){ add_edge(x,y,w); add_edge(y,x,w); } int n,s,t; ll dis[h]; bool ch[h]; void clear(int now){ for(int i=head[now];i;i=last[i]) ch[i]=0,ch[i^1]=0; } void dfs(int now,int fa){ for(int i=head[now];i;i=last[i]){ int nex=to[i]; if(nex^fa) if(dis[nex]>dis[now]+len[i]) clear(nex),dis[nex]=dis[now]+len[i],ch[i]=0,ch[i^1]=1,dfs(nex,now); } } ll d; int main(){ scanf("%d%d%d",&n,&s,&t); for(int i=1,u,v;i<n;i++) scanf("%d%d%lld",&u,&v,&d),add(u,v,d); memset(dis,0x3f,sizeof(dis)); dis[s]=0,dis[t]=0; dfs(s,0),dfs(t,0); ll ans=0; for(int i=1;i<=n;i++) ans+=dis[i]; printf("%lld\n",ans); for(int i=1;i<n;i++) if(ch[i*2]) putchar('1'); else if(ch[i*2+1]) putchar('2'); else putchar('0'); return 0; }完整代码
标签:ch,洛谷,int,题解,ll,tot,nex,P8509,now From: https://www.cnblogs.com/12103h/p/16894668.html