Ser1ousSAM

Grafs

Oct 10th, 2020
68
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int INF = 1000000000;
  5.  
  6. int main() {
  7.     int n, m;
  8.     cin >> n >> m;
  9.     vector < vector < pair<int, int> > > g(n);
  10.     int v, r;
  11.     for (int i=0; i < m; i++) {
  12.         cin >> v >> r;
  13.         g[v].push_back(make_pair(v, r));
  14.     }
  15.     int s = 1; // стартовая вершина
  16.  
  17.     vector<int> d(n, INF), p(n);
  18.     d[s] = 0;
  19.     vector<char> u(n);
  20.     for (int i = 0; i < n; ++i) {
  21.         int v = -1;
  22.         for (int j = 0; j < n; ++j)
  23.             if (!u[j] && (v == -1 || d[j] < d[v]))
  24.                 v = j;
  25.         if (d[v] == INF)
  26.             break;
  27.         u[v] = true;
  28.  
  29.         for (size_t j = 0; j < g[v].size(); ++j) {
  30.             int to = g[v][j].first,
  31.                 len = g[v][j].second;
  32.             if (d[v] + len < d[to]) {
  33.                 d[to] = d[v] + len;
  34.                 p[to] = v;
  35.             }
  36.         }
  37.     }
  38.     for (int i = 0; i < n; ++i) {
  39.         cout << d[i] << " ";
  40.     }
  41.     return 0;
  42. }
RAW Paste Data