给出N个点，M条边。Q次询问

Q次询问每两点之间的最短距离

典型LCA 问题   Marjan算法解

#include "stdio.h"

#include "string.h"

struct Edge

{

    int to,next,len;

}edge[20010];

struct Ques

{

    int to,next,index;

}ques[2000010];

int head[10010],q_head[10010],f[10010],dis[10010];

int vis[10010],ans[1000010];

// vis记录结点是否被遍历过，而且存储结点所在的树是哪颗

// ans记录每一个询问的答案

int n,m,q,tot,q_tot;

void add_edge(int a,int b,int c)

{

    edge[tot].to=b;

    edge[tot].next=head[a];

    edge[tot].len=c;

    head[a]=tot++;

    edge[tot].to=a;

    edge[tot].next=head[b];

    edge[tot].len=c;

    head[b]=tot++;

}

void add_ques(int a,int b,int index)

{

    ques[q_tot].to=b;

    ques[q_tot].next=q_head[a];

    ques[q_tot].index=index;

    q_head[a]=q_tot++;

    ques[q_tot].to=a;

    ques[q_tot].next=q_head[b];

    ques[q_tot].index=index;

    q_head[b]=q_tot++;

}

int find(int w)

{

    if (f[w]==w) return w;

    return f[w]=find(f[w]);

}

void Tarjan(int w,int deep,int root) // w：当前点，deep：当前深度，root：根节点

{

    int i,v;

    f[w]=w;

    vis[w]=root;

    dis[w]=deep;

    for (i=q_head[w];i!=-1;i=ques[i].next)

    {

        v=ques[i].to;

        if (vis[v]==root)

            ans[ques[i].index]=dis[v]+dis[w]-2*dis[find(v)];

    }

    for (i=head[w];i!=-1;i=edge[i].next)

    {

        v=edge[i].to;

        if (vis[v]==-1)

        {

            Tarjan(v,deep+edge[i].len,root);

            f[v]=w;

        }

    }

}

void init()

{

    int i,a,b,c;

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

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

    tot=q_tot=0;

    while (m--)

    {

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

        add_edge(a,b,c);

    }

    for (i=1;i<=q;i++)

    {

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

        add_ques(a,b,i);

    }

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

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

}

int main()

{

    int i;

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

    {

        init();

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

            if (vis[i]==-1)

                Tarjan(i,0,i);

        for (i=1;i<=q;i++)

            if (ans[i]==-1)

                printf("Not connected\n");

            else

                printf("%d\n",ans[i]);

    }

    return 0;

}