HDU 2586 How far away ?
2018-06-17 21:37:51来源:未知 阅读 ()
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18652 Accepted Submission(s):
7268
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int MAXN=1e5+10; 6 inline int read() 7 { 8 char c=getchar();int x=0,f=1; 9 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} 10 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f; 11 } 12 int n,m,S=1; 13 int f[MAXN][21],deep[MAXN],g[MAXN]; 14 struct node 15 { 16 int u,v,w,nxt; 17 }edge[MAXN]; 18 int head[MAXN]; 19 int num=1; 20 inline void add_edge(int x,int y,int z) 21 { 22 edge[num].u=x; 23 edge[num].v=y; 24 edge[num].w=z; 25 edge[num].nxt=head[x]; 26 head[x]=num++; 27 } 28 void dfs(int now) 29 { 30 for(int i=head[now];i!=-1;i=edge[i].nxt) 31 if(deep[edge[i].v]==0) 32 { 33 deep[edge[i].v]=deep[now]+1; 34 f[edge[i].v][0]=now; 35 g[edge[i].v]=g[now]+edge[i].w; 36 dfs(edge[i].v); 37 } 38 39 } 40 inline void pre() 41 { 42 for(int i=1;i<=19;i++) 43 for(int j=1;j<=n;j++) 44 f[j][i]=f[f[j][i-1]][i-1]; 45 } 46 inline int LCA(int x,int y) 47 { 48 if(deep[x]<deep[y]) swap(x,y); 49 for(int i=19;i>=0;i--) 50 if(deep[f[x][i]]>=deep[y]) 51 x=f[x][i]; 52 if(x==y) return x; 53 54 for(int i=19;i>=0;i--) 55 if(f[x][i]!=f[y][i]) 56 x=f[x][i],y=f[y][i]; 57 return f[x][0]; 58 } 59 int main() 60 { 61 int T=read(); 62 while(T--) 63 { 64 n=read();m=read(); 65 memset(head,-1,sizeof(head));num=1; 66 memset(f,0,sizeof(f)); 67 memset(deep,0,sizeof(deep)); 68 for(int i=1;i<=n-1;i++) 69 { 70 int x=read(),y=read(),z=read(); 71 add_edge(x,y,z); 72 add_edge(y,x,z); 73 } 74 deep[S]=1; 75 dfs(S);pre(); 76 while(m--) 77 { 78 int x=read(),y=read(); 79 printf("%d\n",g[x]+g[y]-2*g[LCA(x,y)]); 80 } 81 } 82 83 return 0; 84 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:巧妙取法——最小公倍数
- HDU-2955-Robberies(0-1背包) 2020-03-30
- hdu1455 拼木棍(经典dfs) 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash