SHARE
TWEET

Untitled

a guest Nov 12th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4.  
  5. using namespace std;
  6.  
  7. const long long INF = 6000 * (long long)1e15;
  8. struct edge {
  9.     int s;
  10.     int e;
  11.     int w;
  12.  
  13.     edge(int s_, int e_, int w_) {
  14.         s = s_;
  15.         e = e_;
  16.         w = w_;
  17.     }
  18.  
  19. };
  20.  
  21. long long d[2005][2005];
  22.  
  23.  
  24. long long min(long long a, long long b) {
  25.     if (a > b) return b;
  26.     return  a;
  27. }
  28.  
  29. vector <edge> edges;
  30. vector<vector<pair<int, long long>>> g;
  31.  
  32. vector <bool> used;
  33. void dfs(int v) {
  34.     used[v] = true;
  35.     for (auto u : g[v]) {
  36.         if (!used[u.first]) {
  37.             dfs(u.first);
  38.         }
  39.     }
  40. }
  41.  
  42. int main() {
  43.     int n, m, s;
  44.     cin >> n >> m >> s;
  45.     s--;
  46.     used.assign(n, false);
  47.     g.assign(n, {});
  48.     for (int i = 0; i < m; i++) {
  49.         int st, e;
  50.         long long w;
  51.         cin >> st >> e >> w;
  52.         st--; e--;
  53.         edges.emplace_back(st, e , w);
  54.         g[st].emplace_back(e, w);
  55.  
  56.     }
  57.     for (int i = 0; i < n; i++) {
  58.         for (int j = 0; j <= n; j++) {
  59.             d[i][j] = INF;
  60.         }
  61.     }
  62.     d[s][0] = 0;
  63.  
  64.     vector <int> cycles;
  65.     for (int k = 1; k <= n; k++) {
  66.     for (int i = 0; i < n; i++) {
  67.             d[i][k] = d[i][k - 1];
  68.         }
  69.         for (int v = 0;  v < n; v++) {
  70.             if (d[v][k - 1] == INF) continue;
  71.             for (auto u : g[v]) {
  72.                 if (d[u.first][k] > d[v][k - 1] + u.second) {
  73.                     if (k == n) {
  74.                         cycles.push_back(u.first);
  75.                     }
  76.                     //cout << "s: " << v  << " e: " << u.first <<  " d[v]: " << d[v][k - 1] << " d[e]: " << d[u.first][k] << " w: " << u.second  << endl;
  77.                     d[u.first][k] = d[v][k - 1] + u.second;
  78.              
  79.                 }
  80.             }
  81.         }
  82.     }
  83.     vector <long long> ans(n, INF);
  84.  
  85.     for (int i = 0; i < n; i++) {
  86.         for (int j = 0; j < n; j++) {
  87.             ans[i] = min(ans[i], d[i][j]);
  88.         }
  89.     }
  90.  
  91.     for (int v : cycles) {
  92.         if (!used[v]) {
  93.             dfs(v);
  94.         }
  95.     }
  96.     for (int v = 0; v < n; v++) {
  97.         if (used[v]) {
  98.             cout << "-\n";
  99.             continue;
  100.         }
  101.         if (ans[v] == INF) {
  102.             cout << "*\n";
  103.             continue;
  104.         }
  105.         cout << ans[v] << '\n';
  106.     }
  107.    /* for (int i = 0; i < n; i++) {
  108.         cout << "v: " << i << " d: " << d[i][n - 1] << endl;
  109.     }*/
  110.  
  111.  
  112.  
  113. }
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