我做过的最棘手的一道题了,不是因为难,难就是不懂,而是因为明明思路对了,却调了很久程序没发现自己哪错了。。。。。就连样例都不过
操,别人的代码::::::::::::::::::::::::::::...。。。
突然醒悟了,好像在坐标转换时错了。注意哦,坐标转换的方法。。。
坑了我一晚上。。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cctype>
#include <algorithm>
#define LL unsigned __int64
using namespace std;
const int N= 40100;
int pre[N],rank[N];
struct Edge{
int u,v,c;
char dir;
}edge[N];
struct Quest{
int u,v;
int index,idp;
bool operator <(const Quest &a)const{
if(index<a.index) return true;
return false;
}
}qask[N/4];
struct Node{
int dx,dy;
}node[N];
int ans[N];
int n,m,qk;
int findx(int x){
int r=x;
int tx=node[x].dx,ty=node[x].dy;
while(pre[r]!=-1){
r=pre[r];
tx+=node[r].dx;
ty+=node[r].dy;
}
int dtx,dty,q;
while(x!=r){
q=pre[x];
dtx=node[x].dx,dty=node[x].dy;
node[x].dx=tx,node[x].dy=ty;
pre[x]=r;
tx-=dtx,ty-=dty;
x=q;
}
return r;
}
void Union(int u,int v,int k){
int uf=findx(u);
int vf=findx(v);
pre[uf]=vf;
node[uf].dx=node[v].dx-node[u].dx;
node[uf].dy=node[v].dy-node[u].dy;
switch(edge[k].dir){
case 'N':node[uf].dy+=edge[k].c; break;
case 'S':node[uf].dy-=edge[k].c; break;
case 'W':node[uf].dx+=edge[k].c; break;
case 'E':node[uf].dx-=edge[k].c; break;
}
}
void work(){
int li=0,root1,root2;
for(int i=0;i<qk;i++){
for(int k=li;k<qask[i].index&&k<m;k++){
Union(edge[k].u,edge[k].v,k);
}
root1=findx(qask[i].u);
root2=findx(qask[i].v);
if(root1!=root2){
ans[qask[i].idp]=-1;
}
else {
int a=abs(node[qask[i].u].dx-node[qask[i].v].dx);
int b=abs(node[qask[i].u].dy-node[qask[i].v].dy);
ans[qask[i].idp]=a+b;
}
li=qask[i].index;
}
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++){
pre[i]=-1;
node[i].dx=node[i].dy=0;
}
for(int i=0;i<m;i++){
scanf("%d %d %d %c",&edge[i].u,&edge[i].v,&edge[i].c,&edge[i].dir);
}
scanf("%d",&qk);
for(int i=0;i<qk;i++){
scanf("%d%d%d",&qask[i].u,&qask[i].v,&qask[i].index);
qask[i].idp=i;
}
sort(qask,qask+qk);
work();
for(int i=0;i<qk;i++)
printf("%d\n",ans[i]);
}
return 0;
}