Tuesday, April 30, 2019

[Gym] L. The Shortest Path

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : L. The Shortest Path
Source            : Codeforces Gym
Category          : Graph Theory
Algorithm         : Bellmanford, Find Negative Cycle 
Verdict           : Accepted 

  1. #include "bits/stdc++.h"  
  2.   
  3. using namespace std;  
  4.   
  5. #define ll                  long long int  
  6.   
  7. static const int maxn = 2e3 + 5;  
  8. static const ll inf = (ll)1e18;  
  9.   
  10. struct Node  
  11. {  
  12.       int v;  
  13.       ll w;  
  14.       Node() {}  
  15.       Node(int v = 0, ll w = 0) : v(v), w(w) {}  
  16. };  
  17.   
  18. vector <Node> graph[maxn];  
  19. int tnode, tedge;  
  20. ll dist[maxn], cnt[maxn];  
  21. bool inqueue[maxn];  
  22.   
  23. pair <ll, bool> bellmanford()  
  24. {  
  25.       for (int i = 1; i <= tnode; i++) dist[i] = 0;  
  26.       for (int i = 1; i <= tnode - 1; i++)  
  27.       {  
  28.             for (int u = 1; u <= tnode; u++)  
  29.             {  
  30.                   for (Node p : graph[u])  
  31.                   {  
  32.                         int v = p.v;  
  33.                         ll w = p.w;  
  34.                         if (dist[u] + w < dist[v])  
  35.                         {  
  36.                               dist[v] = dist[u] + w;  
  37.                         }  
  38.                   }  
  39.             }  
  40.       }  
  41.       for (int u = 1; u <= tnode; u++)  
  42.       {  
  43.             for (Node p : graph[u])  
  44.             {  
  45.                   int v = p.v;  
  46.                   ll w = p.w;  
  47.                   if (dist[u] + w < dist[v])  
  48.                   {  
  49.                         return make_pair(0, false); // Negative cycle found  
  50.                   }  
  51.             }  
  52.       }  
  53.       ll mini = inf;  
  54.       for (int i = 1; i <= tnode; i++) mini = min(mini, dist[i]);  
  55.       return make_pair(mini, true);  
  56. }  
  57.   
  58.   
  59. int main()  
  60. {  
  61.       ios_base::sync_with_stdio(false);  
  62.       cin.tie(nullptr);  
  63.       cout.tie(nullptr);  
  64.       cout << fixed << setprecision(15);  
  65.       #ifndef ONLINE_JUDGE  
  66.             freopen("in.txt""r", stdin);  
  67.             // freopen("out.txt", "w", stdout);  
  68.       #endif // ONLINE_JUDGE  
  69.   
  70.       int tc;  
  71.       cin >> tc;  
  72.       for (int tcase = 1; tcase <= tc; tcase++)  
  73.       {  
  74.             for (int i = 1; i < maxn; i++) graph[i].clear();  
  75.             cin >> tnode >> tedge;  
  76.             ll minw = inf;  
  77.             for (int e = 1; e <= tedge; e++)  
  78.             {  
  79.                   int u, v;  
  80.                   ll w;  
  81.                   cin >> u >> v >> w;  
  82.                   graph[u].push_back({v, w});  
  83.                   minw = min(minw, w);  
  84.             }  
  85.             if (minw >= 0)  
  86.             {  
  87.                   cout << minw << '\n';  
  88.                   continue;  
  89.             }  
  90.             pair <ll, bool> ans = bellmanford();  
  91.             if (ans.second == false) cout << "-inf\n";  
  92.             else cout << ans.first << '\n';  
  93.       }  
  94. }  

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.