Description

【题意】20241008scy修改题意
一个二维平面，有 $N$ 个坐标都为整数的点，点编号为 $1$ 到 $N$。
两点的距离为曼哈顿距离。$(x1, y1)$ 和 $(x2, y2)$ 间的曼哈顿距离定义为 $|x1 − x2| + |y1 − y2|$。
现在想要知道只通过前$K$ 条的信息，判断两个点的两点的曼哈顿距离。

【输入格式】
• 第一行：两个整数 $N$ 和 $Q$，1 \le N \le 40000, 1 \le Q \le 50000
• 下来 $Q$ 行。每行三个整数一个字母：$U$，$V$，$L$，$C$。字母$C$是 $E$、$S$、$W$ 和 $N$ 中的一个。表示 点$U$ 在 点$V$ 的东E、南S、西W、北N方向，且距离为$L$。1 \le U, V \le N, 1 \le L \le 1000
• 下来一个整数 $M$，表示询问的次数。
• 下来 $M$ 行。每行一个询问，三个整数 $U$ ， $V$，$K$ ，表示询问的是只通过前 $K$ 条信息，点 $U$ 和 点$V$ 间的曼哈顿距离，1 \le U, V \le N

【输出格式】
• 每个询问输出一行，输出两点间的曼哈顿距离，如果前K条信息还不足以得知答案，输出 −1。

【样例输入】
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6 1
1 4 3
2 6 6

【样例输出】
13
-1
10

【解释】
最后一个询问中，6 和 2 的南北距离为 3，东西距离为 7，故答案为 10

Hint

by hansang:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=4e4+10;
struct node{
    LL x, y;
    node() {x=y=0;}
} d[N];
struct at{int u, v; LL l; char s[5];} a[N];
struct qt{int u, v, k, id;} b[N];
node operator+(node n1, node n2){
    n1.x+=n2.x; n1.y+=n2.y;
    return n1;
}
node operator-(node n1, node n2){
    n1.x-=n2.x; n1.y-=n2.y;
    return n1;
}
bool cmp(qt q1, qt q2){
    return q1.k<q2.k;
}
int fa[N]; LL ans[N]; bool v[N];
int findfa(int x){
    if(fa[x]==x) return fa[x];
    int f=fa[x];
    int tx=findfa(fa[x]);
    d[x]=d[x]+d[f];
    return fa[x]=tx;
}
void merge(int u, int v, LL l, char s[]){
    int tx=findfa(u), ty=findfa(v);
    if(tx==ty) return ;
    fa[tx]=ty; node no;
    if(s[0]=='E') no.x=0, no.y=l;
    if(s[0]=='S') no.x=-l, no.y=0;
    if(s[0]=='W') no.x=0, no.y=-l;
    if(s[0]=='N') no.x=l, no.y=0;
    d[tx]=no-d[ u ]+d[v];
}
int dis(node n1, node n2){
    return abs(n1.x-n2.x)+abs(n1.y-n2.y);
}
int main(){
    int n, q; scanf("%d%d", &n, &q);
    for(int i=1; i<=n; i++) fa[i]=i;
    for(int i=1; i<=q; i++){
        scanf("%d%d%lld%s", &a[i].u, &a[i].v, &a[i].l, a[i].s);
    }
    int m; scanf("%d", &m);
    for(int i=1; i<=m; i++){
        scanf("%d%d%d", &b[i].u, &b[i].v, &b[i].k);
        b[i].id=i;
    }
    sort(b+1, b+m+1, cmp);
    memset(v, 0, sizeof(v)); int now=0;
    for(int i=1; i<=m; i++){
        while(now<=b[i].k) merge(a[now].u, a[now].v, a[now].l, a[now].s), now++;
        int tx=findfa(b[i].u), ty=findfa(b[i].v);
        if(tx!=ty){
            ans[b[i].id]=-1;
        }
        else{
            ans[b[i].id]=dis(d[b[i].u], d[b[i].v]);
        }
    }
    for(int k=1; k<=m; k++) printf("%lld\n", ans[k]);
    return 0;
}