daily pastebin goal
5%
SHARE
TWEET

fifth

a guest May 16th, 2018 115 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <string>
  4. #include <vector>
  5. #include <queue>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. void main() {
  11.     setlocale(LC_ALL, "Russian");
  12.    
  13.     // считываем количество вершин и ребер в графе и номера вершин A и B
  14.     int n, m, a, b;
  15.     cin >> n >> m >> a >> b;
  16.    
  17.     // создаем вектор, в котором будем хранить граф
  18.     vector<vector<bool>> g(n, vector<bool>(n));
  19.    
  20.     // считываем ребра
  21.     for (int i = 0; i < n; i++) {
  22.         int from, to;
  23.         cin >> from >> to;
  24.        
  25.         g[from][to]=true;
  26.         g[to][from]=true;
  27.     }
  28.  
  29.     // создаем вектор для хранения расстояния, заполняем его большими числами
  30.     // так же создаем вектор с предками, заполняем его -1
  31.     vector<int> d(n, 999999), p(n, -1);
  32.     // создаем очередь, в которой будем хранить вершины для обхода
  33.     queue<int> q;
  34.    
  35.     // добавим начало пути в очередь
  36.     q.push(a);
  37.     // длина пути из вершины A в саму себя - ноль
  38.     d[a] = 0;
  39.     // предком у вершины А запишем саму себя для удобства
  40.     p[a] = a;
  41.    
  42.     // пока в очереди есть элементы - выполняем поиск в ширину
  43.     while (!q.empty()) {
  44.         // берем вершину из очереди
  45.         int v = q.front();
  46.         q.pop();
  47.        
  48.         // смотрим всех её соседей
  49.         for (int i = 0; i < n; i++) {
  50.             // если вершина i - сосед, и пусть в неё через вершину v короче, чем тот,
  51.             // что был известен до этого - значит мы нашли новый, более короткий путь в вершину i
  52.             if (g[v][i] && d[v] + 1 < d[i]) {
  53.                 // обновляем расстояние, запоминаем предка и добавляем вершину i в очередь
  54.                 d[i] = d[v] + 1;
  55.                 p[i] = v;
  56.                 q.push(i);
  57.             }
  58.         }
  59.     }
  60.    
  61.     // если у вершины b предок всё так же -1 - значит мы в неё не заходили,
  62.     // и значит пути из A в B нет
  63.     if (p[b] == -1) {
  64.         cout << "Пути нет" << endl;
  65.     } else {
  66.         // если предок не -1, значит путь есть.
  67.         // Будем идти по предкам, пока не дойдем до вершины,
  68.         // предок которой она же сама (а такая у нас только вершина А)
  69.         // таким образом мы восстановим путь из A в B
  70.         vector<int> result;
  71.         int v = b;
  72.         while (p[v] != v) {
  73.             result.push_back(v);
  74.             v = p[v];
  75.         }
  76.         result.push_back(v);
  77.        
  78.         // выводим найденный путь в обратном порядке
  79.         for(int i = result.size() - 1; i >=0; i--) {
  80.             cout << result[i] << " ";
  81.         }
  82.         cout << endl;
  83.     }
  84. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top