Negative Cycle DetectionWhen detecting negative cycles reachable from a starting node, two primary algorithms are used: Bellman-Ford and SPFA (Shortest Path Faster Algorithm).In the Bellman-Ford algorithm, shortest paths are computed over n-1 iterations. If a relaxation is still possible during the...
Consider an air travel network of $n$ cities where passengers have two booking options for any city pair $(i, j)$: a standard economy ticket with price $Y_{i,j}$ or a special transfer-discounted ticket priced at $T_{i,j}$. The discounted fare is only applicable when the ticket is used as part of a t...
A great problem that requires building a graph in a non-obvious way. Problem link At first glance, it's not obvious to build a graph, but with some thought it's not too hard. The idea is to set edge weights to 0 for moving onto lily pads and 1 for moving on to water cells. Then just run Dijkstra. Th...
Shortest Paths Revisited via Floyd-Warshall The problem Luogu P1119 (Post‑Disaster Reconstruction) provides a natural opportunity to exploit the transitive nature of the Floyd‑Warshall algorithm. We are given a graph where certain vertices become usable over time and must answer online queries about...
The Floyd algorithm is a critical component in solving this problem. Its essential to understand the underlying logic of the standard implementation. for(int k=1; k<=n; ++k) for(int i=1; i<=n; ++i) { if(k == i) continue; for(int j=1; j<=n; ++j) { if(k == j || i == j) continue; if(dist[i][j]...
Given four positive integers (x, y, z, H), the goal is to count the number of integers (d) in the range ([0, H]) that can be expressed as (d = a x + b y + c z), where (a, b, c) are non-negative integers. If a value (k) can be written as (k = b y + c z) with non-negative (b) and (c), then (k) is a va...