3336665_ac_969ms_4608k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define maxn 40001
#define maxm 10001

using namespace std;

int n, m;
struct node
{
	int tar;
	int dis;
	char dir;
};

struct Node
{
	int u, v;
};

Node edge[maxn];
int pos[maxn][2];
int father[maxn];
int p[maxn], rank[maxn];
vector <node> tree[maxn];
queue <int> que;

struct NODE
{
	int u, v, id;
};

NODE query[maxm];

char op(char ch)
{
	switch (ch)
	{
	case 'E':	return 'W';
	case 'W':	return 'E';
	case 'S':	return 'N';
	default :	return 'S';
	}
}

int FIND_SET(int x)
{
	if (x!=p[x])
		return p[x] = FIND_SET(p[x]);
	else
		return p[x];
}

void LINK(int x,int y)
{
	if (rank[x] > rank[y])
	{
		p[y] = x;
	}
	else
	{
		p[x] = y;
		if (rank[x] == rank[y])
		{
			rank[y]++;
		}
	}
}

void UNION(int x,int y)
{
	LINK(FIND_SET(x),FIND_SET(y));
}

void bfs()
{
	int i, u;
	node t;

	pos[0][0] = 0;pos[0][1] = 0;
	que.push(0);
	father[0] = -1;
	while (!que.empty())
	{
		u = que.front();
		que.pop();
		for (i = 0; i < tree[u].size(); i++)
		{
			t = tree[u][i];
			if (father[u]==t.tar)
			{
				continue;
			}
			father[t.tar] = u;
			int x, y;
			switch (t.dir)
			{
			case 'E':	x = pos[u][0]+t.dis;y = pos[u][1];break;
			case 'W':	x = pos[u][0]-t.dis;y = pos[u][1];break;
			case 'N':	x = pos[u][0];y = pos[u][1]+t.dis;break;
			case 'S':	x = pos[u][0];y = pos[u][1]-t.dis;break;
			}
			pos[t.tar][0] = x;
			pos[t.tar][1] = y;
			que.push(t.tar);
		}
	}
}

void input()
{
	int i, j; 
	int v, u, w;
	char d[2];
	node t;

	scanf("%d%*s",&n);
	for (i = 1; i < n; i++)
	{
		scanf("%d%d%d%s",&u,&v,&w,d);
		u--;v--;
		edge[i].u = u;
		edge[i].v = v;
		t.tar = v;t.dis = w;t.dir = d[0];
		tree[u].push_back(t);
		t.tar = u;t.dir = op(d[0]);
		tree[v].push_back(t);
	}
	bfs();
	scanf("%d",&m);
	for (i = 0; i < n; i++)
	{
		p[i] = i;
		rank[i] = i;
	}
	for (i = 0; i < m; i++)
	{
		scanf("%d%d%d",&query[i].u,&query[i].v,&query[i].id);
		query[i].u--;query[i].v--;
	}
	for (i = 1, j = 0; i < n&&j < m; i++)
	{
		int a = FIND_SET(edge[i].u);
		int b = FIND_SET(edge[i].v);
		if (a!=b)
		{
			UNION(edge[i].u,edge[i].v);
		}
		if (query[j].id == i)
		{
			while (j < m&&query[j].id==i)
			{
				a = FIND_SET(query[j].u);
				b = FIND_SET(query[j].v);
				if (a!=b)
					puts("-1");
				else
					printf("%d\n",abs(pos[query[j].u][0]-pos[query[j].v][0])+abs(pos[query[j].u][1]-pos[query[j].v][1]));
				j++;
			}
		}
	}
}



int main()
{
	input();
	return 0;
}