#include <stdio.h>
#include <string.h>
struct CIRCLE
{
	int linenum;
	int line[150];
	int color;
	int linecolor[150];
};
struct STATE
{
	int p1,p2;
};

STATE queue[15000];
CIRCLE circle[150];
int N,L,K,Q,M;
int rear,front;
bool used[150][150];
int i,j,k,c;
int count;
int prerear;
int now1,now2;
bool OK;
int main()
{
	//freopen("1.txt","r",stdin);
	scanf("%d%d%d%d",&N,&L,&K,&Q);
	for(i=1;i<=N;i++)
	{
		scanf("%d",&circle[i].color);
		circle[i].linenum=0;
	}
	scanf("%d",&M);
	for(i=0;i<M;i++)
	{
		scanf("%d%d%d",&j,&k,&c);
		circle[j].line[circle[j].linenum]=k;
		circle[j].linecolor[circle[j].linenum]=c;
		circle[j].linenum++;
	}
	front=rear=0;
	prerear=0;
	count=1;
	queue[front].p1=L;
	queue[front].p2=K;
	memset(used,0,sizeof(used));
	OK=0;
	while(front<=rear)
	{
		if(front>prerear)
		{
			prerear=rear;
			count++;
		}
		now1=queue[front].p1;
		now2=queue[front].p2;
		for(i=0;i<circle[now1].linenum;i++)//pawn1 is procceed first
		{
			j=circle[now1].line[i];
			if(circle[now2].color==circle[now1].linecolor[i] && used[j][now2]==0 && now2 != j)
			{
				rear++;
				queue[rear].p1=j;
				queue[rear].p2=now2;
				used[j][now2]=true;
				if(now2==Q || j==Q)
				{
					OK=1;
					goto	END;
				}
			}
		}

		for(i=0;i<circle[now2].linenum;i++)//pawn2 is procceed second
		{
			j=circle[now2].line[i];
			if(circle[now1].color==circle[now2].linecolor[i] && used[now1][j]==0 && now1 != j)
			{
				rear++;
				queue[rear].p2=j;
				queue[rear].p1=now1;
				used[now1][j]=true;
				if(now1==Q || j==Q)
				{
					OK=1;
					goto	END;
				}
			}
		}
		front++;
	}
END:	if(OK==0)
		printf("NO\n");
	else
		printf("YES\n%d\n",count);
	return 0;
}

• 大牛帮忙看看成吗？？我都调了两个钟头了…… (0) byron 2006-07-16 16:43:19
  • 郁闷！先做别的去……就是广搜呀，哪里错了？？搞不明白…… (0) byron 2006-07-16 17:17:59