1708.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"memory.h"
int set[100][100];
int map[100][10000][2];
int path[100];
int n,l,k,q;
int cir[100];

void init()
{int i,m,a,b;
memset(path,0,100*sizeof(int));
memset(set,0,100*100*sizeof(int));

	cin>>n>>l>>k>>q;
	l--;k--;q--;

for(i=0;i<n;i++)cin>>cir[i];
cin>>m;
for(i=0;i<m;i++){cin>>a>>b;a--;b--;
				cin>>map[a][path[a]++][1];
				     map[a][path[a]-1][0]=b;}
}

int queue[10000][3],head,tail;

void find()
{int a,b,c,i,to;
head=0;tail=0;
queue[tail][0]=l;queue[tail][1]=k;
queue[tail][2]=0;
set[l][k]=set[k][l]=1;
tail++;
int key=0;
while(head!=tail&&!key)
{a=queue[head][0];
 b=queue[head][1];
 c=queue[head][2];
 head++;head%=10000;
 for(i=0;i<path[a];i++)
	 if(map[a][i][0]!=b&&cir[b]==map[a][i][1]&&!set[b][map[a][i][0]])
	 {if(map[a][i][0]==q){key=1;break;}
	  to=map[a][i][0];
	  
	  set[b][to]=1;set[to][b]=1;
	  queue[tail][0]=to;queue[tail][1]=b;
	  queue[tail][2]=c+1;
	  tail++;tail%=10000;
	 }
 
 for(i=0;i<path[b]&&!key;i++)
	 if(map[b][i][0]!=a&&cir[a]==map[b][i][1]&&!set[a][map[b][i][0]])
	 {if(map[b][i][0]==q){key=1;break;}
	  to=map[b][i][0];
	 
	  set[to][a]=1;set[a][to]=1;
	  queue[tail][0]=to;queue[tail][1]=a;
	  queue[tail][2]=c+1;
	  tail++;tail%=10000;
	 }
}
if(key){cout<<"YES"<<endl;cout<<c+1<<endl;}
else cout<<"NO"<<endl;

}

int main()
{init();
find();
return 0;
}