Poj Solution 1708

http://poj.org/problem?id=1708

#include<iostream>
#include"memory.h"
using namespace std;
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;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *