inf=INT_MAX 的错误输出

Question

以下代码适用于 Bellman Ford 算法，当我在第 3 行中使用 const int INF=INT_MAX 时输出错误，但当我使用 const int INF=1e9 时输出正确。知道为什么吗？

代码：

#include"bits/stdc++.h"
using namespace std;
const int INF=1e9;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> edges;

    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        edges.push_back({u,v,w});

    }
    int src;
    cin>>src;
    vector<int> dist(n,INF);
    dist[src]=0;
    for(int iter=0;iter<n-1;iter++)
    {
        for(auto e:edges)
        {
            int u=e[0];
            int v=e[1];
            int w=e[2];
            dist[v]=min(dist[v],w+dist[u]);

        }
    }
    for(auto i:dist)
    {
        cout<<i<<" ";
    }

}

示例输入：

5 8

1 2 3

3 2 5

1 3 2

3 1 1

1 4 2

0 2 4

4 3 -3

0 1 -1

0

预期输出： 0 -1 2 -2 1

Answer 1

此处有符号整数溢出 w+dist[u]。简单的修复：

dist[v] = static_cast<int>(min(static_cast<long long>(dist[v]), static_cast<long long>(w) + dist[u]));

inf=INT_MAX 的错误输出

wrong output for inf=INT_MAX

c++

bellman-ford