坑点1:查询的顺序可能是乱序,即后面的I小于前面的I
坑点2:查询的顺序可能会有多个相同的,所以要同时判断
曼哈顿距离需要去维护两个方向上的距离,所以这里的d[x].x
代表着点x
到父节点的x轴
方向上的距离,d[x].y
代表着点x
到父节点的y轴
方向上的距离,在计算的时候仍可参考向量计算方式。
#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 40005;
struct Node{
int a,b,dis,dir;// 0:x轴 1:y轴
}node[N];
struct Query{
int a,b,c,id;
}query[N];
int n,m,k;
int p[N],ans[N];
PII d[N];
int find(int x)
{
if(p[x] != x)
{
int root = find(p[x]);
d[x].x += d[p[x]].x;
d[x].y += d[p[x]].y;
p[x] = root;
}
return p[x];
}
bool cmp(struct Query x,struct Query y)
{
return x.c < y.c;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++ ) p[i] = i;
for(int i = 1;i <= m;i ++ )
{
int a,b,dis;
char op;
cin >> a >> b >> dis >> op;
if(op == 'E') node[i] = {a,b,dis,0};
if(op == 'W') node[i] = {a,b,-dis,0};
if(op == 'N') node[i] = {a,b,-dis,1};
if(op == 'S') node[i] = {a,b,dis,1};
}
cin >> k;
for(int i = 1;i <= k;i ++ )
{
int a,b,c;
cin >> a >> b >> c;
query[i] = {a,b,c,i};
}
sort(query + 1,query + k + 1,cmp);
int t = 1;
for(int i = 1;i <= m;i ++ )
{
int a = node[i].a,b = node[i].b;
int dis = node[i].dis,dir = node[i].dir;
int pa = find(a),pb = find(b);
if(pa != pb)
{
p[pa] = pb;
if(dir == 0)
{
d[pa].x = -d[a].x + dis + d[b].x;
d[pa].y = -d[a].y + d[b].y;
}
else
{
d[pa].x = -d[a].x + d[b].x;
d[pa].y = -d[a].y + dis + d[b].y;
}
}
while(query[t].c == i)
{
int a = query[t].a,b = query[t].b,id = query[t].id;
t ++ ;
if(find(a) != find(b)) ans[id] = -1;
else ans[id] = abs(d[a].x - d[b].x) + abs(d[a].y - d[b].y);
}
}
for(int i = 1;i <= k;i ++ )
cout << ans[i] << endl;
return 0;
}
dalaotql
写的不错,赞一个