[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 

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll                  long long int  
  
static const int maxn = 2e3 + 5;  
static const ll inf = (ll)1e18;  
  
struct Node  
{  
      int v;  
      ll w;  
      Node() {}  
      Node(int v = 0, ll w = 0) : v(v), w(w) {}  
};  
  
vector <Node> graph[maxn];  
int tnode, tedge;  
ll dist[maxn], cnt[maxn];  
bool inqueue[maxn];  
  
pair <ll, bool> bellmanford()  
{  
      for (int i = 1; i <= tnode; i++) dist[i] = 0;  
      for (int i = 1; i <= tnode - 1; i++)  
      {  
            for (int u = 1; u <= tnode; u++)  
            {  
                  for (Node p : graph[u])  
                  {  
                        int v = p.v;  
                        ll w = p.w;  
                        if (dist[u] + w < dist[v])  
                        {  
                              dist[v] = dist[u] + w;  
                        }  
                  }  
            }  
      }  
      for (int u = 1; u <= tnode; u++)  
      {  
            for (Node p : graph[u])  
            {  
                  int v = p.v;  
                  ll w = p.w;  
                  if (dist[u] + w < dist[v])  
                  {  
                        return make_pair(0, false); // Negative cycle found  
                  }  
            }  
      }  
      ll mini = inf;  
      for (int i = 1; i <= tnode; i++) mini = min(mini, dist[i]);  
      return make_pair(mini, true);  
}  
  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
            // freopen("out.txt", "w", stdout);  
      #endif // ONLINE_JUDGE  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            for (int i = 1; i < maxn; i++) graph[i].clear();  
            cin >> tnode >> tedge;  
            ll minw = inf;  
            for (int e = 1; e <= tedge; e++)  
            {  
                  int u, v;  
                  ll w;  
                  cin >> u >> v >> w;  
                  graph[u].push_back({v, w});  
                  minw = min(minw, w);  
            }  
            if (minw >= 0)  
            {  
                  cout << minw << '\n';  
                  continue;  
            }  
            pair <ll, bool> ans = bellmanford();  
            if (ans.second == false) cout << "-inf\n";  
            else cout << ans.first << '\n';  
      }  
}  

[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 

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll                  long long int  
  
static const int maxn = 2e3 + 5;  
static const ll inf = (ll)1e18;  
  
struct Node  
{  
      int v;  
      ll w;  
      Node() {}  
      Node(int v = 0, ll w = 0) : v(v), w(w) {}  
};  
  
vector <Node> graph[maxn];  
int tnode, tedge;  
ll dist[maxn], cnt[maxn];  
bool inqueue[maxn];  
  
pair <ll, bool> spfa()  
{  
      queue <int> PQ;  
      for (int i = 1; i <= tnode; i++)  
      {  
            PQ.push(i);  
            dist[i] = 0;  
            inqueue[i] = 1;  
            cnt[i] = 1;  
      }  
      while (!PQ.empty())  
      {  
            int u = PQ.front(); PQ.pop();  
            inqueue[u] = 0;  
            for (Node p : graph[u])  
            {  
                  int v = p.v;  
                  ll w = p.w;  
                  if (dist[u] + w < dist[v])  
                  {  
                        dist[v] = dist[u] + w;  
                        if (!inqueue[v])  
                        {  
                              cnt[v]++;  
                              inqueue[v] = 1;  
                              PQ.push(v);  
                        }  
                        if (cnt[u] > tnode) return make_pair(0, false); // Negative Cycle found  
                  }  
            }  
      }  
      ll mini = inf;  
      for (int i = 1; i <= tnode; i++) mini = min(mini, dist[i]);  
      return make_pair(mini, true);  
}  
  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
            // freopen("out.txt", "w", stdout);  
      #endif // ONLINE_JUDGE  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            for (int i = 1; i < maxn; i++) graph[i].clear();  
            cin >> tnode >> tedge;  
            ll minw = inf;  
            for (int e = 1; e <= tedge; e++)  
            {  
                  int u, v;  
                  ll w;  
                  cin >> u >> v >> w;  
                  graph[u].push_back({v, w});  
                  minw = min(minw, w);  
            }  
            if (minw >= 0)  
            {  
                  cout << minw << '\n';  
                  continue;  
            }  
            pair <ll, bool> ans = spfa();  
            if (ans.second == false) cout << "-inf\n";  
            else cout << ans.first << '\n';  
      }  
}