Shortest Paths with Negative Edge Weights

Bellman-Ford

Shortest Paths

Solution

Finding Negative Cycles

Solution

As mentioned in cp-algorithms, we relax the edges N times. If we perform an update on the $N$th iteration, there is an negative cycle.

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct edge {
	int from, to;
	ll weight;
};

const int MAXN = 2505;

Simple Linear Programming

You can also use shortest path algorithms to solve the following problem (a very simple linear program).

Given variables $x_1,x_2,\ldots,x_N$ with constraints in the form $x_i-x_j\ge c$, compute a feasible solution.

Resources

Problems

Timeline (USACO Camp):

• equivalent to Timeline (Gold) except $N,C\le 5000$ and negative values of $x$ are possible.

Floyd-Warshall

Solution - APSP

Copy
const int MOD = 1000000007;
const ll INF = 1e18;

int n, m, q;
ll dist[150][150], bad[150][150];

void solve() {
	F0R(i, n) F0R(j, n) dist[i][j] = INF, bad[i][j] = 0;
	F0R(i, n) dist[i][i] = 0;
	F0R(i, m) {

Problems

Modified Dijkstra

The Dijkstra code presented earlier will still give correct results if there are no negative cycles. However, the same running time bound no longer applies, as demonstrated by subtasks 1-6 of the following problem.

This problem forces you to analyze the inner workings of the three shortest-path algorithms we presented here. It also teaches you about how problemsetters could create hack cases!