[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';  
      }  
}  

[Spoj] Wandering Queen

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Wandering Queen
Source            : Spoj
Category          : Graph Theory
Algorithm         : spfa
Verdict           : Accepted 

#include "bits/stdc++.h"
 
using namespace std;
 
#define FOR(i, n)                 for (int i = 1; i <= n; i++)
#define For(i, n)                 for (size_t i = 0; i < n; i++)
 
#define inf                       12345678
 
static const int maxn = 1000 + 5;
 
int dr[] = {0, 0, 1, -1, 1, 1, -1, -1};  // 8 Direction
int dc[] = {1, -1, 0, 0, 1, -1, 1, -1};
 
struct info
{
    int x, y;
    info(int x = 0, int y = 0) : x(x), y(y) {}
};
 
int row, column;
int dis[maxn][maxn];
bool now[maxn][maxn];
char grid[maxn][maxn];
 
bool inside(int r, int c)
{
    return r >= 1 && r <= row && c >= 1 && c <= column;
}
 
int spfa(info src, info des)
{
    FOR(i, row) FOR(j, column) dis[i][j] = inf, now[i][j] = 0;
    queue <info> PQ;
    PQ.emplace(src);
    dis[src.x][src.y] = 0;
    now[src.x][src.y] = 1;
    while(!PQ.empty())
    {
        info u = PQ.front(); PQ.pop();
        now[u.x][u.y] = 0;
        For(i, 8)
        {
            bool push = false;
            int prex = u.x, prey = u.y;
            while (true)
            {
                int x = prex + dr[i];
                int y = prey + dc[i];
                if (!inside(x, y) || grid[x][y] == 'X') break;
                if (dis[x][y] >= dis[u.x][u.y] + 1)
                {
                    dis[x][y] = dis[u.x][u.y] + 1;
                    if (!now[x][y]) now[x][y] = 1, PQ.emplace(x, y);
                    prex = x, prey = y;
                }
                else break;
            }
        }
    }
    if (dis[des.x][des.y] == inf) return -1;
    return dis[des.x][des.y];
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int tc;
    cin >> tc;
    FOR(tcase, tc)
    {
        cin >> row >> column;
        info s, t;
        FOR(i, row)
        {
            FOR(j, column)
            {
                cin >> grid[i][j];
                if (grid[i][j] == 'S') s.x = i, s.y = j;
                if (grid[i][j] == 'F') t.x = i, t.y = j;
            }
        }
        int ans = spfa(s, t);
        cout << ans << endl;
    }
} 

[UVa] 13010 - Galactic taxes

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13010 - Galactic taxes
Source            : UVa Online Judge
Category          : Graph Theory, Search
Algorithm         : spfa, Ternary Search
Verdict           : Accepted  

#include <bits/stdc++.h>  
   
using namespace std;  
   
#define inf             1e13  
   
static const int maxn = 1000 + 5;  
   
struct node  
{  
    int v, A, B;  
    node() {}  
    node(int v, int A, int B)  
    {  
        this->v = v;  
        this->A = A;  
        this->B = B;  
    }  
};  
   
vector <node> g[maxn];  
   
int N, M;  
double dist[maxn];  
bool inQueue[maxn];  
   
double SPFA(double t)  
{  
    for (int i = 1; i < maxn; i++)  
    {  
        dist[i] = inf;  
        inQueue[i] = 0;  
    }  
    queue <int> PQ;  
    PQ.push(1);  
    dist[1] = 0.0;  
    inQueue[1] = 1;  
    while (!PQ.empty())  
    {  
        int u = PQ.front(); PQ.pop();  
        inQueue[u] = 0;  
        for (auto &it : g[u])  
        {  
            double cost = (double)it.A * t + (double)it.B;  
            int v = it.v;  
            if (dist[v] > dist[u] + cost)  
            {  
                dist[v] = dist[u] + cost;  
                if (!inQueue[v])  
                {  
                    inQueue[v] = 1;  
                    PQ.push(v);  
                }  
            }  
        }  
    }  
    return dist[N];  
}  
   
void ternary_search()  
{  
    double low = 0.0;  
    double high = 1440.0;  
    double ans = -inf;  
    for (int tol = 0; tol < 300; tol++)  
    {  
        double mid1 = low + (high - low) / 3.0;  
        double mid2 = high - (high - low) / 3.0;  
        double fmid1 = SPFA(mid1);  
        double fmid2 = SPFA(mid2);  
        ans = max(ans, max(fmid1, fmid2));  
        if (fmid1 < fmid2) low = mid1;  
        else high = mid2;  
    }  
    cout << fixed << setprecision(5) << ans << endl;  
}  
   
int main()  
{  
    //freopen("in.txt", "r", stdin);  
   
    while (cin >> N >> M)  
    {  
        for (int i = 0; i < M; i++)  
        {  
            int u, v, A, B;  
            cin >> u >> v >> A >> B;  
            g[u].push_back({v, A, B});  
            g[v].push_back({u, A, B});  
        }  
        ternary_search();  
        for (int i = 0; i < maxn; i++) g[i].clear();  
    }  
}