为什么 INTMAX_MAX 在这里给出错误的结果？

Question

我遇到了一个问题，要求我找出任意给定顶点对之间最便宜路径的最大值。我为解决方案实施了 Floyd Warshall 算法。但是我的程序中有一个奇怪的错误。我正在使用 intmax_t 来避免溢出，但是如果我使用 INTMAX_MAX 而不是 INT_MAX 来表示两个顶点没有直接连接的无限成本，我会得到错误的答案。为什么会这样？

#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;
}

如果我用 INTMAX_MIN 替换 INT_MIN，用 INTMAX_MAX 替换 INT_MAX，我得到的结果不正确。

示例案例：

使用INT_MAX：http://ideone.com/ffmv7P

使用INTMAX_MAX：http://ideone.com/vjMCuE

附录：该程序是专门为解决竞争性编程问题而编写的。请将您的 "correct coding practice" 建议留给自己。如果您愿意回答，您会发现在这种情况下，预处理器指令对可读性造成的影响很小或没有问题。他们在那里是有原因的，我不傻。如果您没有竞争性编程经验，请不要怪我。谢谢。

Answer 1

您正在添加数字并有溢出的可能性。使用 INT_MAX 时，您使用的数字可能低于 intmax_t 的范围（这是单元格的实际类型）。也就是说 INT_MAX+INT_MAX 很可能适合 intmax_t 而不会溢出，而 INTMAX_MAX+INTMAX_MAX 绝对不会。

您运行进入整数溢出，理论上具有未定义的行为。很可能在现实中它不能很好地与比较一起工作，因为整数溢出会换成负数使得 INTMAX_MAX+INTMAX_MAX 比 INTMAX_MAX 小得多（它甚至可以变成负数）。

如果您的编译器 int 具有相同的范围 intmax_t（这并非不切实际），您的代码在这两种情况下都应该失败。

Answer 2

显然不能将 INTMAX_MAX 存储在 int 类型的变量中。你得到一个溢出，导致未定义的行为。实际上，您通常会得到 INTMAX_MAX 的最后 32 位，它们与 (int) -1 的位模式相同。

另一方面，将 int 与 INTMAX_MAX 进行比较意味着 int 将被转换为 intmax_t，但只要类型不同（实际上它们是不同的），int永远不会等于 INTMAX_MAX。

为什么 INTMAX_MAX 在这里给出错误的结果？

Why does INTMAX_MAX give wrong result here?

c++

numeric-limits