fork download
copy 
  1. /*
  2. Author : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5.  
  6.  
  7. " when you are not practicing someone else is ,
  8.  and the day u meet them u will lose "
  9.  
  10. */
  11. #include<bits/stdc++.h>
  12. #include<stdio.h>
  13. using namespace std;
  14.  
  15. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  16. #define MAX 200050
  17.  
  18. #define ll long long
  19. #define ld long double
  20. #define lli long long int
  21.  
  22. #define pb push_back
  23. #define INF 1000000000000
  24. #define mod 1000000007
  25.  
  26. // trignometric function always give value in Radians only
  27. #define PI acos(-1) //3.1415926535897932384626433832795028
  28. #define dsin(degree) sin(degree*(PI/180.0))
  29. #define dcos(degree) cos(degree*(PI/180.0))
  30. #define dtan(degree) tan(degree*(PI/180.0))
  31.  
  32. #define rsin(radian) sin(radian)
  33. #define rcos(radian) cos(radian)
  34. #define rtan(radian) tan(radian)
  35.  
  36. #define mem0(a) memset(a,0,sizeof(a))
  37. #define mem1(a) memset(a,-1,sizeof(a))
  38. #define memf(a) memset(a,false,sizeof(a))
  39.  
  40. #define loop(i,n)  for (lli i = 0; i < n; i++)
  41. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  42.  
  43. #define all(v) v.begin(),v.end()
  44. #define rall(v) v.rbegin(),v.rend()
  45. #define sz(x) int(x.size())
  46. #define F first
  47. #define S second
  48.  
  49. #define mii map<lli,lli>
  50. #define mci map<char,lli>
  51. #define vi vector<lli>
  52. #define vbool vector<bool>
  53. #define seti set<lli>
  54. #define pii pair<lli,lli>
  55. #define pcc pair<char,char>
  56.  
  57. #define gcd(a,b) __gcd((a),(b))
  58. #define lcm(a,b) (a/gcd(a,b))*b
  59. #define abs(x) ((x < 0)?-(x):x)
  60.  
  61. #define endl '\n'
  62.  
  63. template <typename T>
  64. void print(T x){cout<<x<<endl;}
  65. template <typename T1, typename T2>
  66. void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
  67. template <typename T1, typename T2,typename T3>
  68. void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}
  69.  
  70. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  71. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  72.  
  73. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  74. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  75.  
  76. #define FD(N) fixed<<setprecision(N)
  77.  
  78. #define deb(x) cout<<#x<<" "<<x<<endl;
  79.  
  80. // chandan1,2
  81. void chandan1(){int y=1;return;}
  82. void chandan2(){
  83.         loop(i,10){
  84.         lli x=1;
  85.     }
  86.     return(chandan1());
  87. }
  88.  
  89. //BELLMAN FORD
  90. // check only negative cycle is there or not
  91. void isNegCycle(vector<pii> adj[] , lli src , lli n)
  92. {
  93.  
  94.     vi dist(n+1,INF) , cnt(n+1,0);
  95.  
  96.     vbool vis(n+1,false);
  97.  
  98.     queue<lli> q;
  99.  
  100.     q.push(src);
  101.     dist[src]=0;
  102.     vis[src]=1;
  103.  
  104.     while(!q.empty())
  105.     {
  106.         lli u = q.front(); q.pop();
  107.  
  108.         vis[u] = false;
  109.  
  110.         for (auto edge : adj[u])
  111.         {
  112.             lli child = edge.S;
  113.             lli cost  = edge.F;
  114.  
  115.             if (dist[child] > dist[u] + cost) 
  116.             {
  117.  
  118.                 dist[child] = dist[u] + cost;
  119.  
  120.                 if (!vis[child]) 
  121.                 {
  122.                     q.push(child);
  123.  
  124.                     vis[child] = true;
  125.  
  126.                     cnt[child]++;
  127.  
  128.                     if (cnt[child] > n)
  129.                     {
  130.                         break;
  131.                        //return true; //negative cycle
  132.                     }
  133.                 }
  134.             }
  135.         }
  136.     }
  137.  
  138.    // return false;
  139.    for(lli i=1;i<=n;i++)
  140.    {
  141.        if(dist[i]==INF)
  142.         cout<<30000<<" ";
  143.         else
  144.             cout<<dist[i]<<" ";
  145.    }
  146.  
  147. }
  148.  
  149.  
  150. int main(){
  151. fastio
  152. lli t=1;
  153. //cin>>t;
  154. chandan2();
  155. while(t--) {
  156.     lli n;
  157.     cin>>n;
  158.  
  159.     // vector of pair <cost , node>
  160.     vector<pii> adj[n+1];
  161.  
  162.     lli m;
  163.     cin>>m;
  164.     lli dp[n][n];
  165.     loop(i,n)
  166.         {
  167.             loop(j,n)
  168.             {
  169.                 if(i==j)
  170.                     dp[i][j]=0;
  171.                 else
  172.                     dp[i][j] = INF;
  173.             }
  174.         }
  175.     loop(i,m)
  176.     {
  177.         lli x,y,cost;
  178.         cin>>x>>y>>cost;
  179.         --x;
  180.         y--;
  181.         dp[x][x]=0;
  182.         dp[y][y]=0;
  183.         dp[x][y]=(cost);
  184.         adj[x+1].pb({cost , y+1});
  185.     }
  186.  
  187.     loop(k,n)
  188.     {
  189.         loop(i,n)
  190.         {
  191.             loop(j,n)
  192.             {
  193.                 if(dp[i][k]!=INF and dp[k][j]!=INF )
  194.                 dp[i][j] = min(dp[i][j] , dp[i][k]+dp[k][j]);
  195.             }
  196.         }
  197.     }
  198.     cout<<"By floyd warshall\n";
  199.  
  200.     loop(i,n)
  201.     {
  202.         if(dp[0][i]>30000)
  203.             cout<<30000<<" ";
  204.         else
  205.             cout<<dp[0][i]<<" ";
  206.     }
  207.     cout<<endl;
  208.  
  209. 	cout<<"By bellman ford\n";
  210.  
  211.     isNegCycle(adj,1,n);
  212.   }
  213. return 0;
  214. }
  215.  
Success #stdin #stdout 0s 4344KB
comments (?)
stdin
copy 
4 5
1 2 10
2 3 10
1 3 100
3 1 -10
2 3 1
stdout
copy 
By floyd warshall
0 10 11 30000 
By bellman ford
0 10 11 30000
https://ideone.com/4RgVFP
language:
C++14 (gcc 8.3)
created:
5 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!