| Time Limit: 2000MS | Memory Limit: 30000K | |
| Total Submissions: 6219 | Accepted: 2230 | |
| Case Time Limit: 1000MS | ||
Description
F1 --- (13) ---- F6 --- (9) ----- F3
| |
(3) |
| (7)
F4 --- (20) -------- F2 |
| |
(2) F5
|
F7
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains four space-separated entities, F1,
F2, L, and D that describe a road. F1 and F2 are numbers of
two farms connected by a road, L is its length, and D is a
character that is either ‘N‘, ‘E‘, ‘S‘, or ‘W‘ giving the
direction of the road from F1 to F2.
* Line M+2: A single integer, K (1 <= K <= 10,000), the number of FB‘s
queries
* Lines M+3..M+K+2: Each line corresponds to a query from Farmer Bob
and contains three space-separated integers: F1, F2, and I. F1
and F2 are numbers of the two farms in the query and I is the
index (1 <= I <= M) in the data after which Bob asks the
query. Data index 1 is on line 2 of the input data, and so on.
Output
* Lines 1..K: One integer per line, the response to each of Bob‘s
queries. Each line should contain either a distance
measurement or -1, if it is impossible to determine the
appropriate distance.
Sample Input
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
Sample Output
13
-1
10
Hint
Source
偏移量并查集。
用偏移量保存点和点之间的相对距离，以祖先节点为基准就可以知道两点之间的坐标差。
刚开始想着不压缩路径会更好写，其实不然……
WA到飞起，最后把求相对距离的算式乘了-1，迷一样地过了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int mxn=45000; 8 struct quest{ 9 int a,b; 10 int id; 11 int ti; 12 }que[mxn]; 13 int cmp(const quest a,const quest b){ 14 return a.ti<b.ti; 15 } 16 int ans[mxn]; 17 struct node{ 18 int x,y; 19 int fa; 20 }p[mxn]; 21 int find(int x){ 22 if(p[x].fa==x)return x; 23 int tmp=p[x].fa; 24 p[x].fa=find(p[x].fa); 25 p[x].x+=p[tmp].x; 26 p[x].y+=p[tmp].y; 27 return p[x].fa; 28 } 29 int n,m,R; 30 int f1[mxn],f2[mxn],di[mxn];//修改信息 31 char dr[mxn]; 32 /* 33 void Print(){ 34 for(int i=1;i<=n;i++){ 35 printf("i:%d pos: %d,%d fa:%d\n",i,p[i].x,p[i].y,p[i].fa); 36 } 37 return; 38 }*/ 39 int main(){ 40 scanf("%d%d",&n,&m); 41 int i,j; 42 for(i=1;i<=n;i++) p[i].fa=i; 43 for(i=1;i<=m;i++){ 44 scanf("%d%d%d %c",&f1[i],&f2[i],&di[i],&dr[i]); 45 } 46 scanf("%d",&R); 47 for(i=1;i<=R;i++){scanf("%d%d%d",&que[i].a,&que[i].b,&que[i].ti);que[i].id=i;} 48 sort(que+1,que+R+1,cmp); 49 int tmm=1; 50 for(i=1;i<=R;i++){ 51 while(tmm<=m && tmm<=que[i].ti){ 52 int fa1=find(f1[tmm]); 53 int fa2=find(f2[tmm]); 54 switch(dr[tmm]){ 55 case ‘E‘:{ 56 p[fa2].fa=fa1; 57 p[fa2].x=-p[f2[tmm]].x+p[f1[tmm]].x-di[tmm]; 58 p[fa2].y=-p[f2[tmm]].y+p[f1[tmm]].y; 59 break; 60 } 61 case ‘W‘:{ 62 p[fa2].fa=fa1; 63 p[fa2].x=-p[f2[tmm]].x+p[f1[tmm]].x+di[tmm]; 64 p[fa2].y=-p[f2[tmm]].y+p[f1[tmm]].y; 65 break; 66 } 67 case ‘N‘:{ 68 p[fa2].fa=fa1; 69 p[fa2].x=-p[f2[tmm]].x+p[f1[tmm]].x; 70 p[fa2].y=-p[f2[tmm]].y+p[f1[tmm]].y-di[tmm]; 71 break; 72 } 73 case ‘S‘:{ 74 p[fa2].fa=fa1; 75 p[fa2].x=-p[f2[tmm]].x+p[f1[tmm]].x; 76 p[fa2].y=-p[f2[tmm]].y+p[f1[tmm]].y+di[tmm]; 77 break; 78 } 79 } 80 tmm++; 81 } 82 int fa1=find(que[i].a); int fa2=find(que[i].b); 83 if(fa1!=fa2){ans[que[i].id]=-1;} 84 else ans[que[i].id]=abs(p[que[i].a].x-p[que[i].b].x)+abs(p[que[i].a].y-p[que[i].b].y); 85 } 86 for(i=1;i<=R;i++)printf("%d\n",ans[i]); 87 return 0; 88 }
原文：http://www.cnblogs.com/SilverNebula/p/5937119.html