>>rt

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAX=100010;

struct node{
    int to;
    int weigh;
    int next;
    int ans;
}edges[MAX],que[MAX];
int box1[MAX],box2[MAX];
bool flag[MAX],visit[MAX];

int n,m,p[MAX],dis[MAX];

int find_set(int x)
{
    if(p[x]!=x)
    {
        p[x]=find_set(p[x]);
    }
    return p[x];
}

void lca(int x)
{
    int u,e;
             visit[x]=true;
    p[x]=x;
    for(int i=box1[x];i!=-1;i=edges[i].next)
    {
        u=edges[i].to;
        if(!visit[u])
        {
            dis[u]=dis[x]+edges[i].weigh;
            lca(u);
            p[u]=x;
        }
    }
    flag[x]=true;
    for(int i=box2[x];i!=-1;i=que[i].next)
    {
        u=que[i].to;
        if(flag[u])
        {
            e=find_set(u);
            que[i].ans=dis[u]+dis[x]-2*dis[e];
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int a,b,d,s,k;
    char c[3];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(box1,-1,sizeof(box1));
        memset(box2,-1,sizeof(box2));
        memset(flag,false,sizeof(flag));
        memset(visit,false,sizeof(visit));
        s=0;
        for(int i=0;i<m;++i)
        {
            scanf("%d%d%d%s",&a,&b,&d,c);
            edges[s].to=b;
            edges[s].weigh=d;
            edges[s].next=box1[a];
            box1[a]=s++;
            edges[s].to=a;
            edges[s].weigh=d;
            edges[s].next=box1[b];
            box1[b]=s++;
        }
        scanf("%d",&k);
        s=0;
        for(int i=0;i<k;++i)
        {
            scanf("%d%d",&a,&b);
            que[s].to=b;
            que[s].ans=0;
            que[s].next=box2[a];
            box2[a]=s++;
            que[s].to=a;
            que[s].ans=0;
            que[s].next=box2[b];
            box2[b]=s++;
        }
        dis[1]=0;
        lca(1);
        for(int i=0;i<s;++i)
        {
            if(que[i].ans)
            printf("%d\n",que[i].ans);
        }
    }
    return 0;
}

• Re终于过了，查询中有相同的点，我没有特殊处理，后来者谨慎 (2327) dut200901102 2010-07-13 21:56:09
  • Re:相同点怎么了?? 输0吗?? (0) reimu 2011-12-02 19:42:57