System Of Difference Constraints

#define inf                  1e7
static const int maxn = 1e3 + 5;

struct edge
{
    int u, v, w;
    edge(int uu = 0, int vv = 0, int ww = 0) : u(uu), v(vv), w(ww) {}
};
struct node
{
    int v, w;
    node(int vv = 0, int ww = 0) : v(vv), w(ww) {}
};
vector <edge> edgeList;
vector <node> graph[maxn];
int tnode, tedge;
int dis[maxn], now[maxn], cnt[maxn];

bool spfa(int s = 0)
{
    for (int i = 0; i < maxn; i++)
    {
        dis[i] = inf;
        now[i] = 0;
        cnt[i] = 0;
    }
    queue <int> PQ;
    PQ.push(s);
    dis[s] = 0;
    now[s] = 1;
    cnt[s] = 1;
    while (!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        now[u] = 0;
        if (cnt[u] > tnode) // negative cycle found
            return false;
        for (auto &it : graph[u])
        {
            int v = it.v;
            int w = it.w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                cnt[v]++;
                if (!now[v])
                {
                    now[v] = 1;
                    PQ.push(v);
                }
            }
        }
    }
    return true;
}

bool solve(int m)
{
    for (int i = 0; i < maxn; i++)
        graph[i].clear();
    for (auto &it : edgeList)
    {
        graph[it.v].push_back(node(it.u, it.w-m));
        graph[0].push_back(node(it.u, 0));
        graph[0].push_back(node(it.v, 0));
    }
    return spfa();
}

int main()
{
    while (scanf("%d %d", &tnode, &tedge) == 2)
    {
        edgeList.clear();
        int maxweight = -inf;
        for (int e = 0; e < tedge; e++)
        {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            edgeList.push_back(edge(u, v, w));
            maxweight = max(maxweight, w);
        }
        if (solve(maxweight))
        {
            printf("Infinite\n");
            continue;
        }
        int low = 1;
        int high = maxweight;
        int ans = -1;
        while (low <= high)
        {
            int mid = (low+high)>>1;
            if (solve(mid))
                ans = mid, low = mid+1;
            else
                high = mid-1;
        }
        if (ans == -1)
            printf("No Solution\n");
        else
            printf("%d\n", ans);
    }
}  #define inf                  1e7
static const int maxn = 1e3 + 5;

struct edge
{
    int u, v, w;
    edge(int uu = 0, int vv = 0, int ww = 0) : u(uu), v(vv), w(ww) {}
};
struct node
{
    int v, w;
    node(int vv = 0, int ww = 0) : v(vv), w(ww) {}
};
vector <edge> edgeList;
vector <node> graph[maxn];
int tnode, tedge;
int dis[maxn], now[maxn], cnt[maxn];

bool spfa(int s = 0)
{
    for (int i = 0; i < maxn; i++)
    {
        dis[i] = inf;
        now[i] = 0;
        cnt[i] = 0;
    }
    queue <int> PQ;
    PQ.push(s);
    dis[s] = 0;
    now[s] = 1;
    cnt[s] = 1;
    while (!PQ.empty())
    {
        int u = PQ.front(); PQ.pop();
        now[u] = 0;
        if (cnt[u] > tnode) // negative cycle found
            return false;
        for (auto &it : graph[u])
        {
            int v = it.v;
            int w = it.w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                cnt[v]++;
                if (!now[v])
                {
                    now[v] = 1;
                    PQ.push(v);
                }
            }
        }
    }
    return true;
}

bool solve(int m)
{
    for (int i = 0; i < maxn; i++)
        graph[i].clear();
    for (auto &it : edgeList)
    {
        graph[it.v].push_back(node(it.u, it.w-m));
        graph[0].push_back(node(it.u, 0));
        graph[0].push_back(node(it.v, 0));
    }
    return spfa();
}

int main()
{
    while (scanf("%d %d", &tnode, &tedge) == 2)
    {
        edgeList.clear();
        int maxweight = -inf;
        for (int e = 0; e < tedge; e++)
        {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            edgeList.push_back(edge(u, v, w));
            maxweight = max(maxweight, w);
        }
        if (solve(maxweight))
        {
            printf("Infinite\n");
            continue;
        }
        int low = 1;
        int high = maxweight;
        int ans = -1;
        while (low <= high)
        {
            int mid = (low+high)>>1;
            if (solve(mid))
                ans = mid, low = mid+1;
            else
                high = mid-1;
        }
        if (ans == -1)
            printf("No Solution\n");
        else
            printf("%d\n", ans);
    }
}