SHARE
TWEET

Untitled

a guest Feb 27th, 2020 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MN = 6047;
  8. const long long INF = 1e18 + 42;
  9.  
  10. int n, m, s;
  11. vector<vector<pair<int, long long>>> vert(MN);
  12. int not_shortest[MN];
  13. int relaxed[MN];
  14. int not_reached[MN];
  15.  
  16. void dfs(int src) {
  17.     not_shortest[src] = 1;
  18.     for (int i = 0; i < vert[i].size(); i++) {
  19.         int k = vert[src][i].first;
  20.         if (!not_shortest[k]) {
  21.             dfs(k);
  22.         }
  23.     }
  24. }
  25.  
  26. int main() {
  27.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  28.     cin >> n >> m >> s;
  29.     --s;
  30.     for (int i = 0; i < m; i++) {
  31.         int a, b;
  32.         long long w;
  33.         cin >> a >> b >> w;
  34.         vert[--a].emplace_back(make_pair(--b, w));
  35.     }
  36.     for (int i = 0; i <= n; i++) {
  37.         not_shortest[i] = 0;
  38.         relaxed[i] = 0;
  39.         not_reached[i] = 0;
  40.     }
  41.  
  42.     // Ford-Bellman
  43.     vector<long long> d(n, INF);
  44.     d[s] = 0;
  45.     for (int k = 0; k < n - 1; k++) {
  46.         for (int i = 0; i < n; i++) {
  47.             for (int j = 0; j < vert[i].size(); j++) {
  48.                 if (d[vert[i][j].first] > vert[i][j].second + d[i]) {
  49.                     d[vert[i][j].first] = vert[i][j].second + d[i];
  50.                 }
  51.             }
  52.         }
  53.     }
  54.     // n-тая итерация
  55.     for (int i = 0; i < n; i++) {
  56.         for (int j = 0; j < vert[i].size(); j++) {
  57.             if (d[vert[i][j].first] > vert[i][j].second + d[i]) {
  58.                 relaxed[vert[i][j].first] = 1;
  59.                 d[vert[i][j].first] = vert[i][j].second + d[i];
  60.             }
  61.         }
  62.     }
  63.  
  64.     for (int k = 0; k < n; k++) {
  65.         if (relaxed[k] == 1 && !not_shortest[k]) {
  66.             dfs(k);
  67.         }
  68.     }
  69.  
  70.     for (int i = 0; i < n; i++) {
  71.         if (d[i] >= INF) {       // >= или == ?
  72.             not_reached[i] = 1;
  73.         }
  74.     }
  75.  
  76.     for (int i = 0; i < n; i++) {
  77.         if (not_shortest[i]) {
  78.             cout << '-' << '\n';
  79.         }
  80.         else if (not_reached[i]) {
  81.             cout << '*' << '\n';
  82.         }
  83.         else cout << d[i] << '\n';
  84.     }
  85.  
  86.     return 0;
  87. }
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