fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <ctype.h>
  4. #include <string.h>
  5. #include <unistd.h>
  6.  
  7. #define skipnotdigit(n)   while( 0 == isdigit(*n)) (n)++
  8. #define skipdigit(n)      while( isdigit(*n)) (n)++
  9. #define push(a, b)        {*a = b; a++;} while (0)
  10. #define pop(a, b)         {a--; b = *a;} while (0)
  11.  
  12.  
  13. int main(void)
  14. {
  15.   char input[10000] = {0}; 
  16.   {
  17.     unsigned int i = 0;
  18.     int c;
  19.     while
  20.     (
  21.      ((c = getchar()) != EOF) &&
  22.      (i < sizeof(input)) // Чтобы буфер не переполнили мне тут
  23.     )
  24.     {
  25.       fprintf(stderr,"!%c!", c);
  26.       input[i]=c;
  27.       i++;
  28.     }
  29.     fprintf(stderr,"!%c!", c);
  30.   }
  31.  
  32.   //read(STDIN_FILENO, input, sizeof(input[0])*sizeof(input)); 
  33.  
  34.   unsigned int a;
  35. //  int asd;
  36.   if (sscanf(input, "%u", &a) != 1) // чтение количества вершин в графе
  37.   {
  38.   	return EXIT_FAILURE;
  39.   }
  40.   unsigned int n1;
  41.   void *memmalloc =  malloc(sizeof(unsigned int) * (a * (a + 1) + a + 2 * a));
  42.   //Память для матрицы, расстояний от нулевой вершины и двух стеков.
  43.   if (memmalloc == NULL)
  44.   {
  45.     perror("malloc failed");
  46.     return EXIT_FAILURE;
  47.   }
  48.   unsigned int *matrix = memmalloc;
  49.   unsigned int * mt_p;
  50.   //матрица, которая будет содержать в себе граф
  51.   //и указатель, который будет по матрице бегать
  52.  
  53.   memset(matrix, 0x00, sizeof(unsigned int)* a * (a + 1));
  54.   //malloc не инициализирует память, поэтому надо записать сюда нули
  55.  
  56.   char * inp_p = &input[0]; //указатель на входные данные
  57.  
  58.   //char buffer[8] = {};
  59.   char buffer[9] = {0};
  60.   // временный буфер, который чтобы числа в него читать
  61.   // и чтобы потом через atoi преобразовывать в число
  62.  
  63.   char * buf_p = buffer;
  64.  
  65.  
  66.   skipnotdigit(inp_p);     //Этот кусок кода нужен для того,
  67.   skipdigit(inp_p);        //чтобы пропустить первое число,
  68.                            //задающее количество вершин графа
  69.  
  70.   for(n1 = 0; n1 < a; n1++)
  71.   {
  72.     skipnotdigit(inp_p);
  73.  
  74.     mt_p = matrix + n1 * (a+1);
  75.     do
  76.     {
  77.       do
  78.       {
  79.         *buf_p = *inp_p;  // копирование аскии-кодов циферок в буфер
  80.         buf_p++; inp_p++; // Увеличим и то и другое
  81.       }
  82.       while(isdigit(*inp_p));
  83.  
  84.  
  85.       *mt_p = atoi(buffer);
  86.       buf_p  = buffer;
  87.       memset(buffer, 0x00, sizeof(buffer) * sizeof(buffer[0]));
  88.  
  89.       if (*mt_p == 0)  // Обработка нуля.
  90.       {
  91.         break;      // Если ноль, заполнять вторую строчку
  92.       }
  93.       mt_p++; // Иначе Заполняем следующий элемент в матрице
  94.     } while (1);
  95.  
  96.   }
  97.  
  98.  
  99.   unsigned int *dist = &matrix[a * (a + 1)];
  100.   //Массив с расстояниями до нулевой вершины. Расположен после двумерной матрицы.
  101.  
  102.   memset(dist, 0xFF, sizeof(*dist) * a);
  103.   dist[0]= 0;
  104.  
  105.   unsigned int *stack[2];
  106.   stack[0] = &dist[1 * a]; //Первый стек идет после массива с расстояниями
  107.   stack[1] = &dist[2 * a]; //Второй стек идет после первого стека
  108.  
  109.   stack[0][0] = 0;
  110.   stack[0][1] = 0;
  111.  
  112.   unsigned int *stackp[2];
  113.   stackp[0] = stack[0];
  114.   stackp[1] = stack[1];
  115.  
  116.  
  117.   mt_p = matrix;
  118.  
  119.   unsigned int steps=0;
  120.  
  121.   unsigned char one_zero = 0;
  122.  
  123.   push(stackp[one_zero], 0);
  124.   //нужно обработать то, что связано с самой первой вершиной, которая у нас нулевая
  125.  
  126.  
  127.   do
  128.   {
  129.     steps++;
  130.     do
  131.     {
  132.       pop(stackp[one_zero], n1);
  133.       //n1 - номер вершины. Берем из стека
  134.  
  135.       mt_p = matrix + (a + 1) * n1;
  136.       //ставит указатель на нужную строчку. В строчке список вершин, заканчивающихся нулем
  137.  
  138.       while ( (*mt_p) != 0)
  139.       {  // Пока не появится ноль, означающий что эта вершина больше ни с чем не соединена
  140.         if ( dist[(*mt_p)-1] > steps )
  141.         { // Если до той вершины графа еще не дошагали за меньшее число ходов
  142.           dist[(*mt_p)-1] = steps;
  143.           // Вносим туда наше число шагов
  144.           push(stackp[one_zero^1], (*mt_p)-1); 
  145.           // Вносим номер вершины в стек, чтобы потом посмотреть, с чем соединена та вершина
  146.         }
  147.  
  148.         mt_p++;
  149.         //смотрим, с какой следующей вершина связана эта вершина (если с никаким, *mt_p будет равен нулю )
  150.       }
  151.     } while ( stackp[one_zero] > stack[one_zero] );
  152.     one_zero ^= 1;
  153.     // Переключалка из нуля в единицу и наоборот
  154.  
  155.   } while (stackp[one_zero] > stack[one_zero]);
  156.  
  157.  
  158.   for (unsigned int i = 0; i != a-1; i++)
  159.   {
  160.     printf("%i ", dist[i]);
  161.   }
  162.   printf("\n");
  163.  
  164.   free(memmalloc);
  165.   return EXIT_SUCCESS;
  166. }
Success #stdin #stdout 0s 2428KB
comments (?)
stdin
copy 
5
2 0
1 3 0
2 4 0
3 5 0
4 0
stdout
copy 
0 1 2 3
https://ideone.com/heKtbV
language:
C99 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!