Nur_Mohammed_Mehedy

Bellman–Ford

Apr 20th, 2021
547
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. #pragma GCC optimize("Ofast")
  4. #pragma GCC target("avx,avx2,fma")
  5. #pragma GCC optimization ("unroll-loops")
  6.  
  7. #include<bits/stdc++.h>
  8. #include<string.h>
  9. using namespace std;
  10. #define pb          push_back
  11. #define all(v)      v.begin(),v.end()
  12. #define ya          cout<<"YES"<<endl;
  13. #define no          cout<<"NO"<<endl;
  14. #define ff          first
  15. #define sc          second
  16. #define inf         999999999
  17. #define pi          3.14159265359
  18. #define printv(v)   for(auto x:v)cout<<x<<' ';cout<<endl;
  19. #define takev(v)    for(auto &x:v)cin>>x;
  20. inline  int         random(int a=1,int b=10)
  21. {
  22.     return a+rand()%(b-a+1);
  23. }
  24. typedef long long ll;
  25. inline ll           lcm(ll a,ll b)
  26. {
  27.     return (a*b)/__gcd(a,b);
  28. }
  29. //#define see(x)  cout<<endl<<#x<<" : "<<(x)<<endl;
  30. #define see(args...) \
  31. { \
  32.     string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
  33.     stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);\
  34. }
  35. void err(istream_iterator<string> it) {}
  36. template<typename T, typename... Args>
  37. void err(istream_iterator<string> it, T a, Args... args)
  38. {
  39.     cout<< *it << " = " << a <<",\n"[++it==istream_iterator<string>()];
  40.     err(it, args...);
  41. }
  42. #define scc(n) scanf("%d",&n);
  43. #define sccc(n) scanf("%lld",&n);
  44.  
  45. typedef pair<ll,ll> pll;
  46. typedef pair<int,int> pii;
  47. const int N=5009,mod=998244353;
  48.  
  49. int d[N];
  50. int cost[N][N];
  51. int nodes,edges;
  52. vector< pii >adj;
  53. int main()
  54. {
  55. //    ios::sync_with_stdio(0);
  56. //    cin.tie(NULL);
  57.  
  58.     fill(d,d+N,inf);
  59.  
  60.     scc(nodes)
  61.     scc(edges)
  62.  
  63.     for(int i=0;i<edges;i++)
  64.     {
  65.         int x,y,c;
  66.         scc(x)
  67.         scc(y)
  68.         scc(c)
  69.         adj.pb({x,y});
  70.         cost[x][y] = c;
  71.     }
  72.  
  73.     d[1] = 0;  /// consider 1 as source
  74.  
  75.     for(int i=1;i<=nodes-1;i++)
  76.     {
  77.         for(auto [u,v]:adj)
  78.         {
  79.             if(d[u]+cost[u][v]<d[v])
  80.                 d[v] = d[u] + cost[u][v];
  81.         }
  82.     }
  83.  
  84.     for(auto [u,v]:adj)
  85.     {
  86.         if(d[u]+cost[u][v]<d[v])
  87.         {
  88.             puts("Negative Cycle Detected");
  89.             goto finish;
  90.         }
  91.     }
  92.  
  93.     for(int i=1;i<=nodes;i++)
  94.     {
  95.         printf("Distance From 1 to %d is : %d\n",i,d[i]);
  96.     }
  97.  
  98.     finish: ;
  99.  
  100.  
  101.     return 0;
  102. }
  103.  
  104. /*
  105. 6 6
  106. 1 3 2
  107. 2 3 10
  108. 3 4 1
  109. 1 4 4
  110. 4 5 7
  111. 4 6 5
  112. */
  113.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×