比赛 ZLXOI2015Day2 评测结果 RRRRRRRRRR
题目名称 妹妹的饼干 最终得分 0
用户昵称 ~Love Star 运行时间 0.099 s
代码语言 C++ 内存使用 12.13 MiB
提交时间 2015-10-30 21:11:31
显示代码纯文本
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
int n,m,q;
struct Edge{
	int from,to,cap;
};
struct LCA{
	vector<int> G[maxn];
	vector<Edge> edges;
	int f[maxn][25];
	int d[maxn];
	long long dist[maxn];
	int cnt;
	void init()
	{
		edges.clear();
		for(int i=1;i<=n;i++)
		G[i].clear();
		memset(f,0,sizeof(f));
		memset(d,0,sizeof(d));
		memset(dist,0,sizeof(dist));
		cnt=0;
	}
	void AddEdge(int from,int to,int cap)
	{
		edges.push_back((Edge){from,to,cap});
		edges.push_back((Edge){to,from,cap});
		G[from].push_back(edges.size()-2);
		G[to].push_back(edges.size()-1);
	}
	void dfs(int x,int fa,int sum)
	{
		f[x][0]=fa;
		d[x]=d[fa]+1;
		int y=fa;
		for(int i=1;i<25;i++)
		{
			f[x][i]=f[y][i-1];
			y=f[y][i-1];
		}
		dist[x]=sum;
		for(int i=0;i<G[x].size();i++)
		{
			Edge& e=edges[G[x][i]];
			if(e.to!=fa)
			{
				dfs(e.to,x,sum+e.cap);
			}
		}
	}
	int lca(int x,int y)
	{
		if(d[x]<d[y])
		{
			y^=x;x^=y;y^=x;
		}
		int dis=d[x]-d[y];
		if(dis)
		{
			for(int i=24;i>=0;i--)
			if(dis&(1<<i)) x=f[x][i];
		}
		if(x==y) return y;
		for(int i=24;i>=0;i--)
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
		x=f[x][0];
		return x;
	}
	long long Dis(int x,int y)
	{
		return dist[x]+dist[y]-2*dist[lca(x,y)];
	}
};
LCA g;
int main()
{
	freopen("ThefallingofZLX.in","r",stdin);
	freopen("ThefallingofZLX.out","w",stdout);
	scanf("%d%d",&n,&m);
	g.init();
	int x,y,len;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&len);
		g.AddEdge(x,y,len);
	}
	g.dfs(1,0,0);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d%d",&x,&y);
		printf("%lld\n",g.Dis(x,y));
	}
	return 0;
}