fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. #define rep(i, a, b) for(int i=(a); i<(b); i++)
  5. #define repi(i, a, b) for(int i=(a); i>(b); i--)
  6. #define db(x) (cerr << #x << ": " << (x) << '\n')
  7. #define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
  8. #define cps CLOCKS_PER_SEC
  9. #define tests(t) int t; cin >> t; while(t--)
  10. #define iceil(n, x) (((n) + (x) - 1) / (x))
  11. #define ll long long
  12. #define gcd __gcd
  13. #define eb emplace_back
  14. #define pb push_back
  15. #define pf push_front
  16. #define pob pop_back
  17. #define pof pop_front
  18. #define sz size()
  19. #define all(v) (v).begin(), (v).end()
  20. #define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
  21. #define pii pair<int, int>
  22. #define vi vector<int>
  23. #define vpii vector<pii>
  24. #define vvi vector<vi>
  25. #define fi first
  26. #define se second
  27. #define mt make_tuple
  28. #define pqueue priority_queue
  29. #define bitcount(x) __builtin_popcount(x)
  30. #define PI acos(-1.0)
  31. #define EPS 1e-9
  32. #define mod 998244353
  33. using namespace std;
  34.  
  35. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  36. template <typename Arg1>
  37. void __f(const char* name, Arg1&& arg1){
  38.     cerr << name << " : " << arg1 << '\n';
  39. }
  40. template <typename Arg1, typename... Args>
  41. void __f(const char* names, Arg1&& arg1, Args&&... args){
  42.     const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  43. }
  44.  
  45. template<typename T1, typename T2>
  46. ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << '(' << p.fi << ", " << p.se << ')'; }
  47.  
  48. template<typename T>
  49. void printv(const T& v) { for(auto i : v) cerr << i << ' '; cerr << '\n'; }
  50.  
  51. template<typename T>
  52. using minpq = priority_queue<T, vector<T>, greater<T>>;
  53.  
  54. template<typename T>
  55. using maxpq = priority_queue<T>;
  56.  
  57. //All indexing is 0-based
  58. using namespace __gnu_pbds;
  59. template<class key, class cmp = std::less<key>>
  60. using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  61. //methods: find_by_order(k); & order_of_key(k);
  62. //To make it an ordered_multiset, use pairs of (value, time_of_insertion)
  63. //to distinguish values which are similar
  64.  
  65. template<class key, class value, class cmp = std::less<key>>
  66. using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  67.  
  68. //Returns no. of values x for which ceil(n / x) == y (y must be > 1).
  69. inline ll CC(ll n, ll y) { return iceil(n, y-1) - iceil(n, y); }
  70.  
  71. //Returns no. of values x for which floor(n / x) == y
  72. inline ll FF(ll n, ll y) { return n / y - n / (y+1); }
  73.  
  74. //a and b are assumed to be taken modulo p
  75. inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c; }
  76. inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c; }
  77. inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p; }
  78.  
  79. #define N 505
  80. #define int ll
  81. // #define trace(...) 42
  82.  
  83.  
  84. vector<pair<int, int>> adj[N];
  85. int n, d[N];
  86. const int inf = 1e9;
  87.  
  88. //O(V*E)
  89. //Returns false if there exists a -ve weight cycle; true otherwise.
  90. //Stores shortest dist from src to i in d[i];
  91. bool BellmanFord() {
  92.     for(int step = 0; step < n-1; step++) {
  93.         for(int i = 0; i < n; i++) {
  94.             for(auto p : adj[i]) {
  95.                 int j = p.first, w = p.second;
  96.                 if(d[j] > d[i] + w) {
  97.                     d[j] = d[i] + w;
  98.                 }
  99.             }
  100.         }
  101.     }
  102.  
  103.     for(int i = 0; i < n; i++) {
  104.         for(auto p : adj[i]) {
  105.             int j = p.first, w = p.second;
  106.             if(d[j] > d[i] + w) return 0;
  107.         }
  108.     }
  109.     return 1;
  110. }
  111.  
  112. main()
  113. {   
  114.     #ifndef ONLINE_JUDGE
  115.         freopen("/home/tarun/Desktop/input.txt", "r", stdin);
  116.      // freopen("/home/tarun/Desktop/output.txt", "w", stdout);
  117.     #endif
  118.     sync;
  119.     clock_t clk = clock();
  120.     cerr << "I will return...\n";
  121.  
  122.     int m; cin >> n >> m;
  123.  
  124.     rep(i, 0, m) {
  125.         int u, v, w; cin >> u >> v >> w;
  126.         --u, --v;
  127.         adj[u].pb({v, w});
  128.     }
  129.  
  130.     if(!BellmanFord()) {
  131.         cout << "NO\n"; return 0;
  132.     }
  133.  
  134.     cout << "YES\n";
  135.     for(int i = 0; i < n; i++) {
  136.         cout << d[i] << " \n"[i == n-1];
  137.     }
  138.  
  139.     cerr << "...don't you ever hang your head.\n";
  140.     cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / cps << '\n';
  141. }
  142.  
  143. //Compile using:
  144. //g++ -o filename.exe --std=c++11 filename.cpp
  145. //Use -D CP for defining a macro CP in the local environment
  146.  
  147.  
  148.  
Success #stdin #stdout #stderr 0s 4296KB
comments (?)
stdin
copy 
4 3
1 2 10
2 3 5
4 2 1
stdout
copy 
YES
0 0 0 0
stderr
copy 
I will return...
...don't you ever hang your head.
Time (in ms): 0.028
https://ideone.com/Z5ylfX
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!