pku2834.cpp

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

#include <stdio.h>
#include <string.h>
#define size 10001
int M, R, F, T;

typedef struct 
{
	int p, d;
} Node;

typedef struct 
{
	int id;
	int next;
} Graph;

Node Jon[size], Cely[size];
Graph G[size * 2];
int vday[size];
int v[size];
int Qu[size];
int cnt;

void Insert(int s, int e)
{
	int p = s;
	while (G[p].next != -1)
	{
		p = G[p].next;
	}
	G[cnt].id = e;
	G[p].next = cnt;
	cnt++;
}

void Solve()
{
	int i, j, s, e, p, h;
	//init
	memset(G, -1, sizeof(G));
	memset(vday, -1, sizeof(vday));
	memset(Qu, -1, sizeof(Qu));
	cnt = size;
	//get the road
	scanf("%d", &R);
	for (i = 0; i < R; i++)
	{
		scanf("%d %d", &s, &e);
		Insert(s, e);
		Insert(e, s);
	}
	//get the place Jon visit
	scanf("%d", &F);
	for (i = 0; i < F; i++)
	{
		scanf("%d", &v[i]);
	}
	//get the place Cely Appears
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d %d", &Cely[i].p, &Cely[i].d);
	}
	//BFS
	s = 0;
	e = 1;
	Qu[0] = 0;
	vday[0] = 0;
	while (s < e)
	{
		p = G[Qu[s]].next;
		while (p != -1)
		{
			if (vday[G[p].id] == -1)
			{
				Qu[e] = G[p].id;
				vday[Qu[e]] = vday[Qu[s]] + 5;
				e++;
			}
			p = G[p].next;
		}
		s++;
	}
	//get the place Jon Appears
	Jon[0].p = 0;
	Jon[0].d = 0;
	for (i = 0, j = 1; i < F; i++)
	{
		Jon[j].p = v[i];
		Jon[j].d = Jon[j - 1].d + vday[v[i]];
		j++;
		Jon[j].p = 0;
		Jon[j].d = Jon[j - 1].d + vday[v[i]];
		j++;
	}
	//Meet!
	i = 0, j = 0;//i:Jon j:Cely
	while (i <= 2 * F && j < T)
	{
		if (Jon[i].d == Cely[j].d && Jon[i].p == Cely[j].p)
		{
			printf("%d\n", Jon[i].d);
			return;
		}
		if (Jon[i].d <= Cely[j].d)
		{
			i++;
		}
		else
		{
			j++;
		}
	}
	while (j < T)
	{
		if (Cely[j].p == 0)
		{
			printf("%d\n", Cely[j].d);
			return;
		}
		j++;
	}
	if (j == T)
	{
		printf("Being expected..\n");
		return;
	}
}

int main()
{
	while (EOF != scanf("%d", &M))
	{
		Solve();
	}
	return 0;
}