c++ - 为什么 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

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

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(这并非不切实际)，您的代码在这两种情况下都应该失败。