原题链接
因为POJ之前炸了 所以拖到现在才
带权并查集 记录到根的曼哈顿距离 然后间接算出别的点的
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<queue> #include<vector> #include<climits> #include<string> #include<cstdlib> #include<ctime> #define MOD 1000000007 #define LL long long using namespace std; struct nico { int f1,f2,l; char d; }load[40005]; int n,m,i,j,fat[40005],k,r1,r2,dx[40005],dy[40005],t,p1,p2,q; int abs(int x) { if(x<0) return -x; return x; } int find(int x) { int tmp; if(fat[x]==x) return x; tmp=find(fat[x]); dx[x]+=dx[fat[x]]; dy[x]+=dy[fat[x]]; fat[x]=tmp; return tmp; } int main() { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) fat[i]=i; for(i=1;i<=m;i++) { scanf("%d%d%d",&load[i].f1,&load[i].f2,&load[i].l); cin>>load[i].d; } scanf("%d",&k); j=1; for(i=1;i<=k;i++) { scanf("%d%d%d",&p1,&p2,&q); while(j<=q) { r1=find(load[j].f1); r2=find(load[j].f2); if(r1!=r2) { fat[r1]=r2; dy[r1]=dy[load[j].f2]-dy[load[j].f1]; dx[r1]=dx[load[j].f2]-dx[load[j].f1]; if(load[j].d=='W') dx[r1]-=load[j].l; if(load[j].d=='E') dx[r1]+=load[j].l; if(load[j].d=='S') dy[r1]+=load[j].l; if(load[j].d=='N') dy[r1]-=load[j].l; } j++; } r1=find(p1); r2=find(p2); if(r1!=r2) printf("-1\n"); else { t=abs(dx[p1]-dx[p2])+abs(dy[p1]-dy[p2]); printf("%d\n",t); } } return 0; }