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         : spfa, 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> spfa()  
  24. {  
  25.       queue <int> PQ;  
  26.       for (int i = 1; i <= tnode; i++)  
  27.       {  
  28.             PQ.push(i);  
  29.             dist[i] = 0;  
  30.             inqueue[i] = 1;  
  31.             cnt[i] = 1;  
  32.       }  
  33.       while (!PQ.empty())  
  34.       {  
  35.             int u = PQ.front(); PQ.pop();  
  36.             inqueue[u] = 0;  
  37.             for (Node p : graph[u])  
  38.             {  
  39.                   int v = p.v;  
  40.                   ll w = p.w;  
  41.                   if (dist[u] + w < dist[v])  
  42.                   {  
  43.                         dist[v] = dist[u] + w;  
  44.                         if (!inqueue[v])  
  45.                         {  
  46.                               cnt[v]++;  
  47.                               inqueue[v] = 1;  
  48.                               PQ.push(v);  
  49.                         }  
  50.                         if (cnt[u] > tnode) return make_pair(0, false); // Negative Cycle found  
  51.                   }  
  52.             }  
  53.       }  
  54.       ll mini = inf;  
  55.       for (int i = 1; i <= tnode; i++) mini = min(mini, dist[i]);  
  56.       return make_pair(mini, true);  
  57. }  
  58.   
  59.   
  60. int main()  
  61. {  
  62.       ios_base::sync_with_stdio(false);  
  63.       cin.tie(nullptr);  
  64.       cout.tie(nullptr);  
  65.       cout << fixed << setprecision(15);  
  66.       #ifndef ONLINE_JUDGE  
  67.             freopen("in.txt""r", stdin);  
  68.             // freopen("out.txt", "w", stdout);  
  69.       #endif // ONLINE_JUDGE  
  70.   
  71.       int tc;  
  72.       cin >> tc;  
  73.       for (int tcase = 1; tcase <= tc; tcase++)  
  74.       {  
  75.             for (int i = 1; i < maxn; i++) graph[i].clear();  
  76.             cin >> tnode >> tedge;  
  77.             ll minw = inf;  
  78.             for (int e = 1; e <= tedge; e++)  
  79.             {  
  80.                   int u, v;  
  81.                   ll w;  
  82.                   cin >> u >> v >> w;  
  83.                   graph[u].push_back({v, w});  
  84.                   minw = min(minw, w);  
  85.             }  
  86.             if (minw >= 0)  
  87.             {  
  88.                   cout << minw << '\n';  
  89.                   continue;  
  90.             }  
  91.             pair <ll, bool> ans = spfa();  
  92.             if (ans.second == false) cout << "-inf\n";  
  93.             else cout << ans.first << '\n';  
  94.       }  
  95. }  

No comments:

Post a Comment

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