CODEWITHSUNDEEP
c++numeric-limits
anukul
anukul

Reputation: 1952

Why does INTMAX_MAX give wrong result here?

I came across a problem which asked me to find the maximum of the cheapest paths between any given pair of vertices. I implemented Floyd Warshall algorithm for the solution. But there is one weird error in my program. I'm using intmax_t to avoid overflows, but if I use INTMAX_MAX instead of INT_MAX for infinite cost to denote that two vertices are not connected directly, I get the wrong answer. Why is this happening?

#include <bits/stdc++.h>
using namespace std;
struct _ { ios_base::Init _i; _() { cin.sync_with_stdio(0); cin.tie(0); } } _;

#define endl '\n'
#define int intmax_t
#define in(x) for (auto& i: x)
#define test int _t; cin >> _t; for (int i=1; i<=_t; i++) {

signed main()
{
    int v, e, ans=INT_MIN;
    cin >> v >> e;
    int g[v+1][v+1];
    for (int i=1; i<=v; i++)
        for (int j=1; j<=v; j++)
            g[i][j]=INT_MAX;
    for (int i=0; i<e; i++)
    {
        int x, y, p;
        cin >> x >> y >> p;
        g[x][y]=g[y][x]=p;
    }
    for (int i=1; i<=v; i++)
        for (int j=1; j<=v; j++)
            for (int k=1; k<=v; k++)
                g[j][k]=min(g[j][k], g[j][i]+g[i][k]);
    for (int i=1; i<=v; i++)
        for (int j=1; j<=v; j++)
            if (g[i][j]!=INT_MAX && i!=j)
                ans=max(ans, g[i][j]);
    cout << ans;
}

If I replace INT_MIN by INTMAX_MIN and INT_MAX by INTMAX_MAX, I get incorrect result.

Sample cases:

Using INT_MAX: http://ideone.com/ffmv7P

Using INTMAX_MAX: http://ideone.com/vjMCuE

Addendum: This program was specifically written for the purpose of solving a competitive programming problem. Please keep your "correct coding practice" advice to yourself. If you are willing to answer, you will find that the preprocessor directives cause little or no problem with readability in this case. They are there for a reason, I am not stupid. If you have no competitive programming experience, do not place the blame on me. Thanks.

Upvotes: 0

Views: 721

Answers (2)

skyking
skyking

Reputation: 14359

You're adding numbers and having the possibility for overflow. When using INT_MAX you're initializing the cells with a number that's possibly lower than the range of intmax_t (which is the real type of the cells). That is INT_MAX+INT_MAX is likely to fit into intmax_t without overflow while INTMAX_MAX+INTMAX_MAX definitely don't.

You run into integer overflow which in theory has undefined behaviour. Most probably in reality it will not work well together with comparison since integer overflow will wrap to negative numbers making INTMAX_MAX+INTMAX_MAX much less than INTMAX_MAX (it can even become negative).

If you had a compiler where int has the same range intmax_t (which is not that unrealistic) your code should fail in both cases.

Upvotes: 1

gnasher729
gnasher729

Reputation: 52538

You can obviously not store an INTMAX_MAX in a variable of type int. You get an overflow, which leads to undefined behaviour. In practice, you will often get the last 32 bits of the INTMAX_MAX, which are the same bit pattern as (int) -1.

On the other hand, comparing an int with INTMAX_MAX means the int will be converted to intmax_t, but as long as the types are different (which they are in practice), an int will never, ever be equal to INTMAX_MAX.

Upvotes: 1

Related Questions