fork(3) download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int main() {
  6. const int inf=4000; // задаем бесконечность
  7. int n, start_position, x; // n-количество вершин, вешина от которой мы будем идти, х испозуем для приема матриы смежности
  8. cin>>n>>start_position;
  9. start_position--; //так как в условии счет начинается с единиццы, а в программе с нуля
  10. vector <int> verges [1001]; //задаем массив вектоов где i-ый вектор содерит в себе номера вешин в которые можно попасть с i-ой вершины
  11. for (int i=0; i<n; i++)//заполняем вышеуказанный массив векторов
  12. {
  13. for(int j=0; j<n; j++)
  14. {
  15. cin>>x;
  16. if (x==1)
  17. {
  18. verges[i].push_back(j);
  19. }
  20. }
  21. }
  22. bool *used = new bool [n]; // показывается, применяли ли мы алкоритм для i-ой вершины
  23. for (int i=0; i<n; i++)
  24. {
  25. used[i]=false;
  26. }
  27. int *distances = new int [n]; //задаем массив расстояний где i-ый элемент это расстояние от исходной вершины до i-ой
  28. for (int i=0; i<n; i++)
  29. {
  30. distances[i]=inf;
  31. }
  32. distances[start_position] = 0;
  33. for (int i=0; i<n; i++) //ищем минимальный элемент для которого еще не применяди алгоритм
  34. {
  35. int minimum=inf;
  36. int position = 0;
  37. for (int j=0; j<n; j++)
  38. {
  39. if (distances[j]<minimum && !used[j])
  40. {
  41. minimum=distances[j];
  42. position=j;
  43. }
  44. }
  45. used[position]=true; //запоминаем, что для минимального элемента пименили алгоритм
  46. for (int i=0; i<verges[position].size(); i++) // применяем алгоитм Дейксты
  47. {
  48. distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));
  49. }
  50. }
  51. for (int i=0; i<n; i++)
  52. {
  53. cout<<((distances[i]==inf)?-1:distances[i])<<" ";
  54. }
  55. return 0;
  56. }
Success #stdin #stdout 0s 3464KB
stdin
6 5
0 1 1 0 0 0
1 0 0 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 1 1 0 0
0 1 0 0 0 0
stdout
2 2 1 1 0 -1