Routes With Discounts and Surcharges
Solve this ProblemA transport network has one-way links between stops, some with a discount (a negative price). Given the price matrix, compute the cheapest total price from a starting stop to every stop. If a cycle whose total price is negative can be reached, prices can be driven down forever, and you should return an empty array instead.
Dijkstra's algorithm fails with negative prices. Bellman-Ford relaxes every link n − 1 times and then does one more pass to detect a negative cycle.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 7 stops numbered 0 … n-1; cost is an n × n matrix: cost[u][v] = 100 means there is no one-way link from u to v, otherwise cost[u][v] (−9 … 9, zero allowed) is the price of the link; a negative price is a discount - ◆
cost[u][u] = 100 (no self links) - ◆
0 ≤ src < n is the starting stop - ◆
Return an array where entry i is the cheapest total price from src to stop i, using 1000 for stops that cannot be reached. If a cycle with a negative total price can be reached from src (prices could then be lowered forever), return an empty array
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Route That Never Repeats a Stop
BruteExplore every route from the source that never visits a stop twice, adding prices, and keep the cheapest total for every stop. This gives the true cheapest prices when there is no negative cycle. To notice a negative cycle, check every link (u, v) at the end: if some link still improves a price, the prices could be lowered forever, so return an empty array. The number of routes grows about like n!.
O(n!)O(n)1class Solution {
2 private void explore(int[][] cost, int u, int total, boolean[] onPath, int[] best) {
3 best[u] = Math.min(best[u], total);
4 onPath[u] = true;
5 for (int v = 0; v < cost.length; v++) {
6 if (cost[u][v] != 100 && !onPath[v]) {
7 explore(cost, v, total + cost[u][v], onPath, best);
8 }
9 }
10 onPath[u] = false;
11 }
12
13 public int[] routeCosts(int[][] cost, int src) {
14 int n = cost.length;
15 int INF = Integer.MAX_VALUE;
16 int[] best = new int[n];
17 Arrays.fill(best, INF);
18 explore(cost, src, 0, new boolean[n], best);
19 for (int u = 0; u < n; u++) {
20 if (best[u] == INF) continue;
21 for (int v = 0; v < n; v++) {
22 if (cost[u][v] != 100 && best[u] + cost[u][v] < best[v]) return new int[0];
23 }
24 }
25 for (int i = 0; i < n; i++) {
26 if (best[i] == INF) best[i] = 1000;
27 }
28 return best;
29 }
30}Optimal — Bellman-Ford
OptimalA cheapest route without a cycle visits at most n stops, i.e. uses at most n − 1 links. So repeat n − 1 times: try to improve the price of every stop v through every link (u, v) whose start u already has a price. After these rounds all prices are final, unless a negative cycle is reachable. One more pass detects that: if some link still improves a price, a negative cycle is reachable and the answer is an empty array. Otherwise unreachable stops get 1000. Unlike Dijkstra, the algorithm works with negative prices.
O(n³) with a matrix (O(n · E) with lists)O(n)1class Solution {
2 public int[] routeCosts(int[][] cost, int src) {
3 int n = cost.length;
4 int INF = Integer.MAX_VALUE;
5 int[] dist = new int[n];
6 Arrays.fill(dist, INF);
7 dist[src] = 0;
8 for (int round = 1; round < n; round++) {
9 for (int u = 0; u < n; u++) {
10 if (dist[u] == INF) continue;
11 for (int v = 0; v < n; v++) {
12 if (cost[u][v] != 100 && dist[u] + cost[u][v] < dist[v]) {
13 dist[v] = dist[u] + cost[u][v];
14 }
15 }
16 }
17 }
18 for (int u = 0; u < n; u++) {
19 if (dist[u] == INF) continue;
20 for (int v = 0; v < n; v++) {
21 if (cost[u][v] != 100 && dist[u] + cost[u][v] < dist[v]) return new int[0];
22 }
23 }
24 for (int i = 0; i < n; i++) {
25 if (dist[i] == INF) dist[i] = 1000;
26 }
27 return dist;
28 }
29}