zoj 3195 Design the city LCA Tarjan

题目大意：

求三点之间的最短距离

思路：

有了两点之间的最短距离求法，不难得出：

对于三个点我们两两之间求最短距离得到 d1 d2 d3

那么最短距离就是 d = ( d1 + d2 + d3 ) / 2

要注意每个数组的范围大小，因为这个问题手抖敲错，TLE+RE一整页/(ㄒoㄒ)/~~
用前向星来保存边和询问，空间卡的也很严
如下图所示：所求路线为紫色，等于蓝色+黄色+绿色之和的一半

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 50005;

const int maxm = 70005;

struct node1 {

    int next,to,w;

} e[maxn*2];

struct node2 {

    int next,to,id;

} q[maxm*6];

int n,m,head1[maxn],head2[maxn],cnt1,cnt2,vis[maxn],f[maxn],res[maxm*6],dist[maxn];

inline void add1(int u, int v, int w) {

    e[cnt1].to=v;

    e[cnt1].w=w;

    e[cnt1].next=head1[u];

    head1[u]=cnt1++;

}

inline void add2(int u, int v, int id) {

    q[cnt2].to=v;

    q[cnt2].id=id;

    q[cnt2].next=head2[u];

    head2[u]=cnt2++;

}

inline void init() {

    cnt1=cnt2=0;

    memset(head1,-1,sizeof(head1));

    memset(head2,-1,sizeof(head2));

    memset(vis,0,sizeof(vis));

}

inline int Find(int x) {

    return x == f[x] ? x : f[x] = Find(f[x]);

}

inline void tarjan(int s) {

    vis[s]=1;

    f[s]=s;

    int t;

    for(int i=head1[s]; i!=-1; i=e[i].next) {

        if(!vis[t=e[i].to]) {

            dist[t]=dist[s]+e[i].w;

            tarjan(t);

            f[t]=s;

        }

    }

    for(int i=head2[s]; i!=-1; i=q[i].next)

        if(vis[t=q[i].to])

            res[q[i].id]=dist[s]+dist[t]-2*dist[Find(t)];

}

int main() {

    int cnt=0,u,v,w,x,y,z;

    while(~scanf("%d",&n)) {

        init();

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

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

            add1(u,v,w);

            add1(v,u,w);

        }

        scanf("%d",&m);

        m*=3;

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

            scanf("%d %d %d",&x,&y,&z);

            add2(x,y,i);

            add2(y,x,i);

            ++i;

            add2(x,z,i);

            add2(z,x,i);

            ++i;

            add2(y,z,i);

            add2(z,y,i);

        }

        dist[0]=0;

        tarjan(0);

        if(!cnt) cnt++;

        else printf("\n");

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

            printf("%d\n",(res[i]+res[i+1]+res[i+2])/2);

            i+=2;

        }

    }

    return 0;

}

巴特西

zoj 3195 Design the city LCA Tarjan

题目大意：

思路：

代码：

最新文章

热门文章