How far away ? HDU
2021/5/30 18:21:50
本文主要是介绍How far away ? HDU,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LCA应用求最短路
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int N=40005; int T,n,m,ans,tot; struct node{ int to,next,w; }edge[N<<1]; int head[N],dep[N]; int f[N][30],dis[N][30]; void init(){ tot=0; memset(edge,0,sizeof(edge)); memset(head,-1,sizeof(head)); memset(dep,0,sizeof(dep)); memset(dis,0,sizeof(dis)); } void add(int u,int v,int w){ edge[tot].to=v; edge[tot].next=head[u]; edge[tot].w=w; head[u]=tot++; } void dfs(int u,int fa){ f[u][0]=fa; dep[u]=dep[fa]+1; for(int j=1;(1<<j)<=dep[u];j++){ f[u][j]=f[f[u][j-1]][j-1]; dis[u][j]=dis[u][j-1]+dis[f[u][j-1]][j-1]; } for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v!=fa){ dis[v][0]=edge[i].w; dfs(v,u); } } } int lca(int u,int v){ if(dep[u]<dep[v]) swap(u,v); if(dep[u]!=dep[v]){ for(int j=20;j>=0;j--){ if(dep[f[u][j]]>=dep[v]){ ans+=dis[u][j]; u=f[u][j]; } } } if(u==v) return ans; for(int j=20;j>=0;j--){ if(f[u][j]!=f[v][j]){ ans+=dis[u][j]; ans+=dis[v][j]; u=f[u][j]; v=f[v][j]; } } return ans+dis[u][0]+dis[v][0]; } int main(){ scanf("%d",&T); while(T--){ init(); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<n;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } dfs(1,0); for(int i=1;i<=m;i++){ ans=0; int x,y; scanf("%d%d",&x,&y); printf("%d\n",lca(x,y)); } } return 0; }
这篇关于How far away ? HDU的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行