话说这一题我曾经写过，结果今天比赛的时候还是写错了。

这一题思路还是挺好想的吧，我们先写一遍最大生成树，然后做一遍LCA。

 至于这一题我是怎么错的呢。。。

 从下午查到现在，终于查出来了。很细节的一个错误。主要还是LCA写的不熟练，打错了一个字符。

int LCA(int x,int y){    if(depth[x]
    
     =depth[y])ans=min(ans,dist[x][i]),x=f[x][i];    if(x==y)return ans;    per(i,LOG-1,0)if(f[x][i]!=f[y][i])ans=min(ans,min(dist[x][i],dist[y][i])),x=f[x][i],y=f[y][i];    ans=min(ans,min(dist[x][0],dist[y][0]));    return ans;}
    

这个里面第4行里面if里 depth[f[x][i]]>=depth[y]，在考试时打成了depth[f[x][i]]<=depth[y]，导致WA了19个点，拿了可怜的5分。

顺便纪念一下20170810测试因为一共打错6个字符由本来能ak的变成可怜的245

AC代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;#define rep(i,a,n) for(register int i=(a);i<=(n);++i)#define per(i,a,n) for(register int i=(a);i>=(n);--i)#define fec(i,x) for(register int i=head[x];i;i=Next[i])#define debug(x) printf("debug:%s=%d\n",#x,x)#define mem(a,x) memset(a,x,sizeof(a))template
        
         inline void read(A&a){a=0;A f=1;int c=0;while(c<'0'||c>'9'){c=getchar();if(c=='-')f*=-1;}while(c>='0'&&c<='9'){a=a*10+c-'0';c=getchar();}a*=f;}template
         
          inline void read(A&a,B&b){read(a);read(b);}template
          
           inline void read(A&a,B&b,C&c){read(a);read(b);read(c);}const int maxn=10000+7,maxm=50000+7,LOG=20+1,INF=0x7f7f7f7f;struct Edge{ int u,v,w;}e[maxm];inline bool comp(const Edge &x,const Edge &y){ return x.w>y.w;}int n,m,q,x,y;int depth[maxn],f[maxn][LOG],dist[maxn][LOG];int u[maxn<<1],v[maxn<<1],w[maxn<<1],Next[maxn<<1],head[maxn],tot;inline void addedge(int x,int y,int z){ u[++tot]=x;v[tot]=y;w[tot]=z; Next[tot]=head[x];head[x]=tot;}int father[maxn];int find(int x){return x==father[x]?x:father[x]=find(father[x]);}inline void Union(int x,int y){if(find(x)!=find(y))father[find(y)]=find(x);}inline void UFS_init(){rep(i,1,n)father[i]=i;}void Kruskal(){ UFS_init(); sort(e+1,e+m+1,comp); rep(i,1,m){ int x=e[i].u,y=e[i].v,z=e[i].w; if(find(x)!=find(y)){ Union(x,y); addedge(x,y,z); addedge(y,x,z); } }}void dfs(int x){ depth[x]=depth[f[x][0]]+1; rep(i,1,LOG-1)f[x][i]=f[f[x][i-1]][i-1],dist[x][i]=min(dist[f[x][i-1]][i-1],dist[x][i-1]); fec(i,x){ int y=v[i]; if(depth[y])continue; f[y][0]=x;dist[y][0]=w[i]; dfs(y); }}int LCA(int x,int y){ if(depth[x]
           
            =depth[y])ans=min(ans,dist[x][i]),x=f[x][i];// debug(ans); if(x==y)return ans; per(i,LOG-1,0)if(f[x][i]!=f[y][i])ans=min(ans,min(dist[x][i],dist[y][i])),x=f[x][i],y=f[y][i]; ans=min(ans,min(dist[x][0],dist[y][0])); return ans;}void Init(){ mem(dist,0x7f); read(n,m); rep(i,1,m)read(e[i].u,e[i].v,e[i].w);}void Work(){ Kruskal();// rep(i,1,n)if(!depth[i])dfs(i); dfs(1); read(q); rep(i,1,q){ read(x,y); if(find(x)!=find(y))printf("%d\n",-1); else printf("%d\n",LCA(x,y)); }}int main(){// freopen("truck.in","r",stdin);// freopen("truck.out","w",stdout); Init(); Work(); fclose(stdin);fclose(stdout); return 0;}