graph/math - System of difference Constraints

/*

        System of difference Constraints
* Given Some inequality on some variable (Xi , Xj , …. ) in form Xj – Xi <= W
* We need to determine whether we can assign values to variables so that all the given inequality is satisfiable or not ? If satisfiable, then output A solution.

Solution:
Building Constraints graph:
1. For each variable we create a vertex.
2. For each in-equality, Xj – Xi <= W , We give an edge (Vi,Vj) with cost W
3. Create a source vertex (S) and give an edge (S,Vi) with cost = 0

* If the graph contains any negative cycle, then there is no solution. Otherwise, We have a solution for each variable and
for each variable (Xi):
    Xi = Shortest Path distance of Vi from the Source vertex in Constraint Graph.
Shortest Path can be calculated from Bellman-Ford algorithm.
Other Results from The constraint Graph:
# Bellman-Ford maximizes x1 + x2 + …. + xn subject to the constraints xj – xi ≤ wij and xi ≤ 0
# Bellman-Ford also minimizes maximum{xi} – minimum {xi}

Example Problem:
x1 - x2 <= 0
x1 - x5 <= -1
x2 - x5 <= 1
x3 - x1 <= 5
x4 - x1 <= 4
x4 - x3 <= -1
x5 - x3 <= -3
x5 - x4 <= -3

Using BellMen-Ford Algorithm:
x = {5,  3, 0,  1,  4}

*/

#include <bits/stdc++.h>
using namespace std;
int n = 5;  // Number of Variables.

vector<pair<int,int > >G[505];
int d[505];
bool inq[505];
int Times[505];
bool spfa()
{
    queue<int>q;
    for(int i = 1;i <= n; i ++ ) {
        d[i]= 0;
        q.push(i);
        inq[i] = 1;
        Times[i] = 1;
    }

    while(!q.empty()){
        int u = q.front(); q.pop();
        inq[u] = 0;
        for(int i = 0; i < G[u].size(); i ++ ) {
            int v = G[u][i].first, w = G[u][i].second;
            if(d[v] > d[u] + w) {
                d[v] = d[u]  + w;
                if(inq[v] == 0) {
                    inq[v] = 1;
                    q.push(v);
                    Times[v] ++;

                    if(Times[v] > n+2 ) return 0;
                }

            }
        }
    }
    return 1;
}
int main()
{
    G[2].push_back(make_pair(1,0)); // x1-x2<=0
    G[5].push_back(make_pair(1,-1));//..
    G[5].push_back(make_pair(2,1));
    G[1].push_back(make_pair(3,5));
    G[1].push_back(make_pair(4,4));
    G[3].push_back(make_pair(4,-1));
    G[3].push_back(make_pair(5,-3));
    G[4].push_back(make_pair(5,-3));
    bool flag = spfa();
    if(flag) {
        for(int i = 1; i<= n;i ++) {
            printf("X%d = %d\n",i,d[i]);
        }
    }
    else printf("No Solution\n");
    /* Expected Output
    X1 = -5
    X2 = -3
    X3 = 0
    X4 = -1
    X5 = -4
    */
}