在火炉做网站公园坐什么车,wordpress怎么恢复自带主题,盐城网页优化公司,logo一键生成器哪个好正题 题目大意
一个n-1个点的有向无环图#xff0c;给出若干个点#xff0c;要求依次到达的最少时间。 解题思路
有向无环图我们可以把其看做一颗树#xff0c;然后每次用LCA求两个点之间的距离#xff0c;然后把所有距离统计一下就是结果。 代码
#includecstdio给出若干个点要求依次到达的最少时间。 解题思路
有向无环图我们可以把其看做一颗树然后每次用LCA求两个点之间的距离然后把所有距离统计一下就是结果。 代码
#includecstdio
#define min(a,b) ab?a:b
using namespace std;
struct line{int next,to;
}a[60001],num[60001];
int father[30001],n,m,q,p,v[30001],tot,ls[30001],t,x,y,in[30001];
int last,ls1[30001],tot2,nber,sum,w[30001],d[30001],ans[30001];
void addl(int x,int y)//加边
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void addn(int x,int y)//表示要求这两个点的距离
{num[tot2].toy;num[tot2].nextls1[x];ls1[x]tot2;
}
int find(int x)//并查集
{return xfather[x]?x:father[x]find(father[x]);
}
void tarjan(int x)
{v[x]1;for (int ils[x];i;ia[i].next){int ya[i].to;if (v[y]) continue;d[y]d[x]1;//计算深度tarjan(y);//tarjan子节点father[y]x;}for (int ils1[x];i;inum[i].next){int ynum[i].to,idw[i];if (v[y]2)ans[id]min(ans[id],d[x]d[y]-d[find(y)]*2);//计算距离}v[x]2;
}
int main()
{scanf(%d,n);for (int i1;in;i)father[i]i;for (int i1;in;i){scanf(%d%d,x,y);addl(x,y);addl(y,x);}scanf(%d,m);last1;for (int i1;im;i){scanf(%d,x);ans[i]130;addn(x,last);w[tot2]i;addn(last,x);w[tot2]i;ans[i]lastx?0:ans[i];lastx;}tarjan(1);for (int i1;im;i)sumans[i];printf(%d,sum);
}
