Bellman-Ford
O(n·m)Single-source shortest paths that tolerates negative edge weights: relax every edge n−1 times. A further improving pass means a negative cycle is reachable. Slower than Dijkstra, so use it only when negatives (or cycle detection) are actually in play.
// use it on
CSES: High Score ↗
Longest path with possible positive cycles: negate the weights and it becomes shortest path with negative-cycle detection.
// the code
// edges {u, v, w}; returns dist, or {} if a negative cycle is reachable
vector<long long> bellman_ford(int n, int src,
vector<array<long long, 3>>& edges) {
const long long INF = LLONG_MAX / 4;
vector<long long> dist(n, INF);
dist[src] = 0;
for (int i = 0; i < n - 1; i++)
for (auto& [u, v, w] : edges)
if (dist[u] < INF && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
for (auto& [u, v, w] : edges) // n-th pass = negative cycle check
if (dist[u] < INF && dist[u] + w < dist[v]) return {};
return dist;
}// more shortest paths