题目描述
对于 n(<100000)个点 n-1 条掉权值的边，有 m 个询问，每条询问求两个结点之间的路径上边权的最小值
输入
第一行 n，表示结点个数，接下来 n-1 行，每行 a b w 表示 a 与 b 之间有一条权值为 w的双向边
第 n+1 行：m 表示询问的个数，接下来 m 行，每行一个询问 a 和 b
输出
对于每个询问，输出两个结点的路径上边权的最小值
样例输入
10 1 4 11161 3 8 7244 5 9 635 1 10 23999 10 6 23998 7 5 16083 4 3 7145 1 7 20425 3 2 25701 14 1 5 9 3 3 1 7 5 9 1 5 1 1 7 3 1 1 8 1 3 7 6 5 7 7 1 1 7
样例输出
16083 635 7145 16083 635 16083 20425 7145 7145 7145 20425 16083 20425 20425
题解：
发个模版，坑爹数据，dfs栈溢出，于是改成bfs
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=,INF=;
int head[N],num=;
struct Lin
{
int next,to,dis;
}a[N<<];
void init(int x,int y,int z)
{
a[++num].next=head[x];
a[num].to=y;
a[num].dis=z;
head[x]=num;
}
int gi(){
int str=,f=;char ch=getchar();
while(ch>'' || ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();
return str*f;
}
int n,fa[N][],dis[N][],dep[N],q[N];
void bfs()
{
dep[]=;
int t=,sum=,x,u;
q[]=;
while(t!=sum)
{
x=q[++t];
for(int i=head[x];i;i=a[i].next)
{
u=a[i].to;
if(dep[u])continue;
q[++sum]=u;dep[u]=dep[x]+;
dis[u][]=a[i].dis;fa[u][]=x;
}
}
}
int maxdep;
void prework()
{
for(int j=;j<=maxdep;j++)
for(int i=;i<=n;i++)
fa[i][j]=fa[fa[i][j-]][j-];
for(int j=;j<=maxdep;j++)
for(int i=;i<=n;i++)
dis[i][j]=min(dis[i][j-],dis[fa[i][j-]][j-]);
}
void Clear()
{
for(int j=;j<=maxdep;j++)
for(int i=;i<=n;i++)dis[i][j]=INF;
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
int deep=dep[x]-dep[y];
int ans=INF;
for(int i=maxdep;i>=;i--)
{
if(deep&(<<i))
{
if(dis[x][i]<ans)ans=dis[x][i];
x=fa[x][i];
}
}
if(x==y)return ans;
for(int i=maxdep;i>=;i--)
{
if(fa[x][i]!=fa[y][i])
{
if(dis[x][i]<ans)ans=dis[x][i];
if(dis[y][i]<ans)ans=dis[y][i];
x=fa[x][i];y=fa[y][i];
}
}
return min(ans,min(dis[x][],dis[y][]));
}
int main()
{
n=gi();
maxdep=log(n)/log()+;
int x,y,z;
Clear();
int ca;
for(int i=;i<n;i++)
{
x=gi();y=gi();z=gi();
init(x,y,z);init(y,x,z);
}
bfs();
prework();
int m=gi();
while(m--)
{
x=gi();y=gi();
ca=lca(x,y);
printf("%d\n",lca(x,y));
}
return ;
}