pku2831.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <algorithm>
#define ONLINE

#ifndef ONLINE
#include <time.h>
#endif

using namespace std;

typedef struct 
{
	int id;
	int ds;
	int next;
} GraphNode;

typedef struct 
{
	int s, e, l;
} Edge;

Edge e0[100001], e1[100001];
GraphNode G[3500];
int D[1001][1001];
int hd[1001];
int N, M, Q;
int cnt;
int v[1001];

bool cmp(const Edge &a, const Edge &b)
{
	return a.l < b.l;
}

int GetID(int x)
{
	return hd[x] ? hd[x] = GetID(hd[x]) : x;
}

int Max(int x, int y)
{
	return x > y ? x : y;
}

void Insert(int x)
{
	int s, e, l, p;
	s = e0[x].s;
	e = e0[x].e;
	l = e0[x].l;
	
	p = s;
	while (G[p].next)
	{
		p = G[p].next;
	}
	G[p].next = cnt;
	G[cnt].id = e;
	G[cnt].ds = l;
	cnt++;

	p = e;
	while (G[p].next)
	{
		p = G[p].next;
	}
	G[p].next = cnt;
	G[cnt].id = s;
	G[cnt].ds = l;
	cnt++;
}

void DFS(int s, int e, int d)
{
	int p;
	D[s][e] = d;
	v[e] = 1;
	p = G[e].next;
	while (p)
	{
		if (!v[G[p].id])
		{
			DFS(s, G[p].id, Max(d, G[p].ds));
		}
		p = G[p].next;
	}
}

void Solve()
{
	int i, j, hs, he, w, d;
	for (i = 0; i < M; i++)
	{
		scanf("%d %d %d", &e0[i].s, &e0[i].e, &e0[i].l);
		e1[i].s = e0[i].s;
		e1[i].e = e0[i].e;
	}
	sort(e0, e0 + M, cmp);
	memset(hd, 0, sizeof(hd));
	memset(G, 0, sizeof(G));
	cnt = N + 10;
	for (i = 1, j = 0; i < N && j < M; j++)
	{
		hs = GetID(e0[j].s);
		he = GetID(e0[j].e);
		if (hs != he)
		{
			i++;
			hd[he] = hs;
			Insert(j);
		}
	}
	for (i = 1; i <= N; i++)
	{
		memset(v, 0, sizeof(v));
		DFS(i, i, 0);
	}
	for (i = 0; i < M; i++)
	{
		e1[i].l = D[e1[i].s][e1[i].e];
	}
	for (i = 0; i < Q; i++)
	{
		scanf("%d %d", &w, &d);
		puts(d <= e1[w - 1].l ? "Yes" : "No");
	}
}

int main()
{

#ifndef ONLINE
	freopen("PKU2831.in", "r", stdin);
	clock_t start = clock();
#endif
	while (EOF != scanf("%d %d %d", &N, &M, &Q))
	{
		Solve();
	}	
#ifndef ONLINE
	printf("TIME:%dms\n", clock() - start);
#endif
	return 0;
}