Advertisement
Guest User

Great Escape

a guest
Feb 4th, 2015
256
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. bool A[3500][3500];
  5.  
  6. int main()
  7. {  int i,n,m,j,k,a,b,s,t;
  8.    
  9.    cin>>n>>m;
  10.    
  11.    for(i=0;i<3500;i++)
  12.    for(j=0;j<3500;j++)
  13.    A[i][j]=0;
  14.    
  15.    
  16.    for(i=0;i<m;i++)
  17.    { cin>>a>>b;
  18.      a--;
  19.      b--;
  20.      A[a][b]=1;
  21.      A[b][a]=1;
  22.      }
  23.      
  24.      cin>>s>>t;
  25.      
  26.      s--;
  27.      t--;
  28.      
  29.      int d[3500];
  30.      
  31.      for(i=0;i<3500;i++)
  32.      d[i]=3600;
  33.      
  34.      d[s]=0;
  35.      
  36.      int Q[3500],H=0,T=0;
  37.      
  38.      Q[T]=s;
  39.      
  40.      while(T>=H)
  41.      {   j=Q[H];
  42.          for(k=0;k<n;k++)
  43.          { if(A[j][k]==1 && d[k]==3600)
  44.            { d[k]=d[j]+1;
  45.              Q[++T]=k;
  46.              }
  47.              }
  48.          H++;
  49.          }
  50.          if(d[t]!=3600)
  51.          cout<<d[t];
  52.          else cout<<0;
  53.          
  54.          }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement