zoj 3195

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3320

离线算法RE了..

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<math.h>

#include<algorithm>

using namespace std;

const int N = ;

const int M =;

struct Edge{

    int u,v,w,next;

}e[*N];

struct Q_Edge{

    int u,v,next,lca;

}eq[*M];

int head[N];

int _head[N];

int dis[N];

int vis[N];

int ances[N];

int father[N];

void addedge(int u,int v,int w,int &k){

    e[k].u = u;e[k].v = v;e[k].w= w;

    e[k].next = head[u];head[u]=k++;

}

void add_qedge(int u,int v,int &k){

    eq[k].u = u;eq[k].v = v;eq[k].lca = -;

    eq[k].next = _head[u];_head[u]=k++;

}

int _find(int u){

    if(u==father[u]) return father[u];

    return father[u] = _find(father[u]);

}

void unions(int u,int v){

    int x = _find(u),y = _find(v);

    father[x]=y;

}

void Targin(int u){

    vis[u] = true;

    ances[u]=father[u] = u;

    for(int k = head[u];k!=-;k=e[k].next){

        if(!vis[e[k].v]){

            int v = e[k].v,w = e[k].w;

            dis[v] = dis[u]+w;

            Targin(v);

            unions(v,u);

            ances[_find(u)] = u;

        }

    }

    for(int k = _head[u];k!=-;k=eq[k].next){

        if(vis[eq[k].v]){

            int v = eq[k].v;

            eq[k].lca = eq[k^].lca = ances[_find(v)];

        }

    }

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF){

        memset(head,-,sizeof(head));

        memset(_head,-,sizeof(_head));

        int tot=;

        for(int i=;i<n;i++){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            addedge(u,v,w,tot);

            addedge(v,u,w,tot);

        }

        tot = ;

        int m;

        scanf("%d",&m);

        for(int i=;i<m;i++){

            int a,b,c;

            scanf("%d%d%d",&a,&b,&c);

            add_qedge(a,b,tot);

            add_qedge(b,a,tot);

            add_qedge(a,c,tot);

            add_qedge(c,a,tot);

            add_qedge(b,c,tot);

            add_qedge(c,b,tot);

        }

        memset(vis,,sizeof(vis));

        dis[]=;

        Targin();

        int a[];

        for(int i=;i<m;i++){

            int s = i*;

            a[] = dis[eq[s].u]+dis[eq[s].v]-*dis[eq[s].lca];  ///a->b

            a[] = dis[eq[s+].u]+dis[eq[s+].v]-*dis[eq[s+].lca]; ///a->c

            a[] = dis[eq[s+].u]+dis[eq[s+].v]-*dis[eq[s+].lca]; ///b->c

            //sort(a,a+3);

            printf("%d\n",(a[]+a[]+a[])/);

        }

        printf("\n");

    }

}