学步园

带权并查集

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int f[40010];
int s1[40010],s2[40010];  //s1为水平，s2为竖直
int ans[10010];
struct Road{
    int u,v,c;
    char dir;
}road[40010];
struct Query{
    int u,v,id;
    int num;
}query[10010];
void init(int n){
    for(int i=1;i<=n;i++){
        f[i]=i;
        s1[i]=s2[i]=0;
    }
}
bool cmp(Query a,Query b){
    return a.id<b.id;
}
int find(int u){
    if(f[u]!=u){
        int tem=f[u];
        f[u]=find(tem);
        s1[u]+=s1[tem];
        s2[u]+=s2[tem];
    }
    return f[u];
}
void Union(int i){
    int u=find(road[i].u);
    int v=find(road[i].v);
    if(u!=v){
        f[u]=v;
        if(road[i].dir=='E'){
            s1[u]=-s1[road[i].u]+road[i].c+s1[road[i].v];
            s2[u]=-s2[road[i].u]+s2[road[i].v];
        }
        else if(road[i].dir=='W'){
            s1[u]=-s1[road[i].u]-road[i].c+s1[road[i].v];
            s2[u]=-s2[road[i].u]+s2[road[i].v];
        }
        else if(road[i].dir=='N'){
            s1[u]=-s1[road[i].u]+s1[road[i].v];
            s2[u]=-s2[road[i].u]+road[i].c+s2[road[i].v];
        }
        else if(road[i].dir=='S'){
            s1[u]=-s1[road[i].u]+s1[road[i].v];
            s2[u]=-s2[road[i].u]-road[i].c+s2[road[i].v];
        }
    }
}
int main(){
    int n,m,i,j,k;
    int now,u,v;
    char dir;
    scanf("%d %d",&n,&m);
    init(n);
    for(i=1;i<=m;i++)
        scanf("%d %d %d %c",&road[i].u,&road[i].v,&road[i].c,&road[i].dir);
    scanf("%d",&k);
    for(i=1;i<=k;i++){
        scanf("%d %d %d",&query[i].u,&query[i].v,&query[i].id);
        query[i].num=i;
    }
    sort(query+1,query+1+k,cmp);
    now=1;
    for(i=1;i<=m;i++){
        Union(i);
        while(query[now].id==i && now<=k){
            u=find(query[now].u);
            v=find(query[now].v);
            if(u==v)
                ans[query[now].num]=abs(s1[query[now].u]-s1[query[now].v])+abs(s2[query[now].u]-s2[query[now].v]);
            else
                ans[query[now].num]=-1;
            now++;
        }
        if(now==k+1)
            break;
    }
    for(i=1;i<=k;i++)
        printf("%d\n",ans[i]);
    return 0;
}