比赛 |
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;
}