Guest User

Great Escape

a guest
Oct 9th, 2016
36
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  Created By: Malvika Joshi
  3.  Problem: GREATESC
  4.  Link: http://opc.iarcs.org.in/index.php/problems/GREATESC
  5. */
  6.  
  7. #include <stdio.h>
  8. #include <limits.h>
  9.  
  10. #define INF -1
  11. int n;
  12. int D[4000];
  13. int Q[4000];
  14. int A[4000][4000];
  15.  
  16. void BFS(int b){
  17.     int H = 0;
  18.     int T = -1;
  19.     int j,k;
  20.     D[b] = 0;
  21.  
  22.     Q[T+1] = b;
  23.     T = T+1;
  24.  
  25.     while(T>=H){
  26.         j = Q[H];
  27.  
  28.         for (k = 0;k < n; k++){
  29.             if(A[j][k] == 1 && D[k] == INF){
  30.                 D[k] = D[j]+1;
  31.                 Q[T+1] = k;
  32.                 T = T+1;
  33.             }
  34.         }
  35.  
  36.         H = H+1;
  37.     }
  38. }
  39.  
  40. int main(){
  41.     int m;
  42.     scanf("%d%d",&n,&m);
  43.     int i,j;
  44.     int a,b,s,t;
  45.  
  46.     for(i = 0;i < n; i++){
  47.         D[i] = INF;
  48.     }
  49.  
  50.     for(i = 0;i < n; i++){
  51.         for(j = 0;j < n; j++){
  52.             A[i][j] = 0;
  53.         }
  54.     }
  55.  
  56.     for(i = 0;i < m; i++){
  57.         scanf("%d%d",&a,&b);
  58.         A[a-1][b-1] = 1;
  59.         A[b-1][a-1] = 1;
  60.     }
  61.  
  62.  
  63.     scanf("%d%d",&s,&t);
  64.  
  65.  
  66.     if(s > 0 && t > 0 && s <= n && t <= n){
  67.         s--;
  68.         t--;
  69.         BFS(s);
  70.  
  71.         if(D[t] == INF){
  72.             printf("0");
  73.         }else {
  74.             printf("%d",D[t]);
  75.         }
  76.     }else {
  77.         printf("0");
  78.     }
  79.  
  80.  
  81.     return 0;
  82. }
RAW Paste Data