> >>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:相同点怎么了?? 输0吗?? (0) reimu 2011-12-02 19:42:57