Don't we have to check for dist[it.u] != INF before adding it.wt. Because if we have negative weight this will become less to INF, and can change the dist[it.v]?
like code may be :
for(int i = 1;i<=N-1;i++) { for(auto it: edges) { if(dist[it.u] != INF && (dist[it.u] + it.wt) < dist[it.v]) { dist[it.v] = dist[it.u] + it.wt; } } }
Don't we have to check for dist[it.u] != INF before adding it.wt. Because if we have negative weight this will become less to INF, and can change the dist[it.v]?
like code may be :
for(int i = 1;i<=N-1;i++) { for(auto it: edges) { if(dist[it.u] != INF && (dist[it.u] + it.wt) < dist[it.v]) { dist[it.v] = dist[it.u] + it.wt; } } }