Advertisement
stas224

Декстра - восстановление пути

May 25th, 2022
643
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. #include<set>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int inf = (1 << 31) - 1;
  9. int main()
  10. {
  11.     int n, start, finish;
  12.     cin >> n >> start >> finish;
  13.     start--; finish--;
  14.     vector <vector<pair<int, int>>> g(n);
  15.     for (int i = 0; i < n; i++)
  16.     {
  17.         for (int j = 0; j < n; j++)
  18.         {
  19.             int w;
  20.             cin >> w;
  21.             if (w != -1 && i != j)
  22.             {
  23.                 g[i].push_back({ j,w });
  24.             }
  25.         }
  26.     }
  27.  
  28.     vector <int> r(n, inf);
  29.     vector <int> p(n);
  30.     r[start] = 0;
  31.     set<pair<int, int>>s;
  32.     s.insert({ 0,start });
  33.     while (!s.empty())
  34.     {
  35.         int rmin = s.begin()->first;
  36.         int cur = s.begin()->second;
  37.         s.erase(s.begin());
  38.         for (pair<int, int> to : g[cur])
  39.         {
  40.             if (r[cur] + to.second < r[to.first])
  41.             {
  42.                 r[to.first] = r[cur] + to.second;
  43.                 p[to.first] = cur;
  44.                 s.insert({ r[to.first], to.first });
  45.             }
  46.         }
  47.     }
  48.     if (r[finish] == inf)
  49.         cout << -1;
  50.     else
  51.     {
  52.         vector<int> path;
  53.         for (int v = finish; v != start; v = p[v])
  54.             path.push_back(v + 1);
  55.         path.push_back(start + 1);
  56.         reverse(path.begin(), path.end());
  57.         for (int i = 0; i < path.size(); i++)
  58.             cout << path[i] << ' ';
  59.     }
  60. }
  61.  
Advertisement
RAW Paste Data Copied
Advertisement