大佬:
你的边没有插入成双向的
dfs里的head要改成head1
改好的代码(AC):
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node
{
int u,v,w,next;
} edge[1000001],edge1[1000001];
int n,m,q;
int depth[100001],father[1000001][21],dis[1000001];//lca
int fa[1000001];//kruskal
int num_edge,num_edge1,head[1000001],head1[1000001];
void add_edge(int u,int v,int w)
{
edge[++num_edge].u=u;
edge[num_edge].v=v;
edge[num_edge].w=w;
edge[num_edge].next=head[u];
head[u]=num_edge;
}
void add1_edge(int u,int v,int w)
{
edge1[++num_edge1].u=u;
edge1[num_edge1].v=v;
edge1[num_edge1].w=w;
edge1[num_edge1].next=head1[u];
head1[u]=num_edge1;
}
//------------------kruskal----------------------
bool cmp(node a,node b)
{
return a.w>b.w;
}
int find(int x)
{
if(fa[x]!=x)
{
fa[x]=find(fa[x]);
}
return fa[x];
}
void kruskal()
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
sort(edge+1,edge+2*m+1,cmp);
for(int i=1;i<=2*m;i++)
{
int xx=find(edge[i].u);
int yy=find(edge[i].v);
if(xx!=yy)
{
add1_edge(edge[i].u,edge[i].v,edge[i].w);
add1_edge(edge[i].v,edge[i].u,edge[i].w);
fa[yy]=xx;
}
}
}
//-------------------lca------------------------------------
void dfs(int u)
{
for(int j=1; j<=14; j++)
{
father[u][j]=father[father[u][j-1]][j-1];
}
for(int j=head1[u];j;j=edge1[j].next)
{
int v=edge1[j].v;
int w=edge1[j].w;
if(v!=father[u][0])
{
father[v][0]=u;
dis[v]=w;
depth[v]=depth[u]+1;
dfs(v);
}
}
}
int up(int v,int d)
{
for(int i=14; i>=0; i--)
{
if(d&(1<<i))v=father[v][i];
}
return v;
}
int lca(int u,int v)
{
if(depth[u]>depth[v])
{
swap(u,v);
}
int d=depth[v]-depth[u];
v=up(v,d);
if(v==u)return u;
for(int i=14; i>=0; i--)
{
if(father[u][i]!=father[v][i])
{
u=father[u][i];
v=father[v][i];
}
}
return father[u][0];
}
//--------------------------求解-----------------------
int cal(int x,int y)
{
int a=2147483647;
int b=2147483647;
int l=lca(x,y);
for(int i=x;i!=l;i=father[i][0])
{
a=min(a,dis[i]);
}
for(int i=y;i!=l;i=father[i][0])
{
b=min(b,dis[i]);
}
return min(a,b);
}
//-----------------主函数--------------------------------------
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z);
add_edge(y,x,z);
}
kruskal();
for(int i=1;i<=n;i++)
{
if(!depth[i])
{
father[i][0]=i;
dfs(i);
}
}
scanf("%d",&q);
for(int i=1; i<=q; i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(find(x)!=find(y))
{
printf("-1\n");
continue;
}
printf("%d\n",cal(x,y));
}
}
```
by ezoixx130 @ 2017-12-07 22:23:42