SHARE
TWEET

Untitled

reiziger Nov 12th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _FORTIFY_SOURCE 0
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC optimize("no-stack-protector")
  4. #pragma GCC optimize("unroll-loops")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  6. #pragma GCC optimize("fast-math")
  7.  
  8. #include <iostream>
  9. #include <math.h>
  10. #include <algorithm>
  11. #include <iomanip>
  12. #include <vector>
  13. #include <set>
  14. #include <map>
  15. #include <deque>
  16. #include <stack>
  17. #include <unordered_map>
  18. #include <unordered_set>
  19.  
  20. using namespace std;
  21.  
  22. typedef long long ll;
  23. typedef long double ld;
  24. typedef pair<ll, ll> pl;
  25. typedef pair<ld, ld> pd;
  26.  
  27. const ll N = 1 * 1e7 + 10;
  28. const ll M = 2e3 + 100;
  29. const ll INF = 1e18 + 100;
  30. const ll NO_EDGE = 100000;
  31.  
  32. #define x first
  33. #define y second
  34. #define pb push_back
  35.  
  36. ll a[M][M];
  37. vector<bool> used;
  38. vector<vector<ll>> g;
  39.  
  40. void dfs(ll v) {
  41.     used[v] = true;
  42.  
  43.     for (auto to : g[v]) {
  44.         if (!used[to]) {
  45.             dfs(to);
  46.         }
  47.     }
  48. }
  49.  
  50. struct edge {
  51.     ll a, b, cost;
  52.  
  53.     edge(ll a, ll b, ll cost) : a(a), b(b), cost(cost) {}
  54. };
  55.  
  56. vector<edge> edges;
  57. vector<ll> d, d1;
  58.  
  59. int main() {
  60.     ll n, m, s;
  61.     cin >> n >> m >> s;
  62.     s--;
  63.     used.resize(n);
  64.     g.resize(n);
  65.  
  66.     for (int i = 0; i < m; i++) {
  67.         ll x, y, z;
  68.         cin >> x >> y >> z;
  69.         x--, y--;
  70.         g[x].pb(y);
  71.  
  72.         edges.pb(edge(x, y, z));
  73.     }
  74.  
  75.  
  76.     d.resize(n, INF);
  77.  
  78.     d[s] = 0;
  79.  
  80.     set<ll> noPath;
  81.     for (int i = 0; i < n; i++) {
  82.         for (auto edge : edges) {
  83.             if (d[edge.a] != INF) {
  84.                 if (d[edge.b] > d[edge.a] + edge.cost) {
  85.                      d[edge.b] = d[edge.a] + edge.cost;
  86.                      if (i == n - 1) {
  87.                          noPath.insert(edge.b);
  88.                      }
  89.                 }
  90.             }
  91.         }
  92.     }
  93.  
  94.     for (auto v : noPath) {
  95.         if (!used[v]) {
  96.             dfs(v);
  97.         }
  98.     }
  99.  
  100.     for (int i = 0; i < n; i++) {
  101.         if (used[i]) {
  102.             cout << '-' << endl;
  103.         } else if (d[i] == INF) {
  104.             cout << '*' << endl;
  105.         } else {
  106.             cout << d[i] << endl;
  107.         }
  108.     }
  109. }
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