| Time Limit: 2000MS | Memory Limit: 30000K | |
| Total Submissions: 8503 | Accepted: 3062 | |
| 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
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} #define MAX INT_MAX #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl using namespace std; int fa[41000],d1[41000],d2[41000]; struct node { int l,r; int len; char c; }v[41000]; struct query { int a,b; int state; int nub,cun; //nub用来进行第二次sort，cun是存答案的 }q[41000]; bool cmp(query x,query y) { return x.state < y.state; } bool cmp2(query x,query y) { return x.nub < y.nub; } int Find(int x) { if(x == fa[x]) return x; int root = Find(fa[x]); d1[x] += d1[fa[x]]; d2[x] += d2[fa[x]]; return fa[x] = root; } void solve(int x,int y,int len,char c) { int fx = Find(x),fy = Find(y); fa[fy] = fx; if(c == ‘E‘) { d1[fy] = d1[x] + len - d1[y]; d2[fy] = d2[x] - d2[y]; } else if(c == ‘W‘) { d1[fy] = d1[x] - len - d1[y]; d2[fy] = d2[x] - d2[y]; } else if(c == ‘N‘){ d1[fy] = d1[x] - d1[y]; d2[fy] = d2[x] + len - d2[y]; } else if(c == ‘S‘){ d1[fy] = d1[x] - d1[y]; d2[fy] = d2[x] - len - d2[y]; } } int ask(int x,int y) { int fx = Find(x); int fy = Find(y); if(fx != fy) return -1; int temp = 0; temp += abs(d1[x] - d1[y]) + abs(d2[x] - d2[y]); // if(d1[x] * d1[y] > 0) temp += abs(d1[x] - d1[y]); // else temp += abs(d1[x]) + abs(d1[y]); // if(d2[x] * d2[y] > 0) temp += abs(d2[x] - d2[y]); // else temp += abs(d2[x]) + abs(d2[y]); return temp; } int main() { // freopen("C:\\Users\\方瑞\\Desktop\\input.txt","r",stdin); // freopen("C:\\Users\\方瑞\\Desktop\\output.txt","w",stdout); int n,m,k,tail; scanf("%d%d",&n,&m); FOR(i,1,n) fa[i] = i; FOR(i,1,m) scanf("%d%d%d %c",&v[i].l,&v[i].r,&v[i].len,&v[i].c); scanf("%d",&k); FOR(i,1,k) { scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].state); q[i].nub = i; } sort(q+1,q+1+k,cmp); tail = 1; for(int i=1;i<=m;++i) { int l = v[i].l; int r = v[i].r; char c = v[i].c; int len = v[i].len; solve(l,r,len,c); while(q[tail].state <= i && tail <= k) { int x = q[tail].a; int y = q[tail].b; q[tail].cun = ask(x,y); tail++; } } sort(q+1,q+1+k,cmp2); FOR(i,1,k) printf("%d\n",q[i].cun); }
原文：https://www.cnblogs.com/jrfr/p/11409737.html