wrong output for inf=INT_MAX

Question

Below code is for Bellman Ford algorithm and it gives wrong output when I use const int INF=INT_MAX but correct output when I use const int INF=1e9 in line number 3. Any idea why?

Code:

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

}

Sample Input:

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

Expected Output: 0 -1 2 -2 1

Answer 1

Signed integer overflow here w+dist[u]. The simple fix:

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