Minimum Cost to reach destination
Problem Statement:
Ram is current at city 1 and wants to reach city N. While crossing cities he can either go from city i to city 1+1 by spending
cost c_i or use a bridge that connects city i to city j ( >1). Each bridge has its own travel cost Ram doesn't likes to travel
from bridges much so he decides not to take more than k bridges during his journey
Since Ram is on a tight budget can you help Ram find out the minimum cost to reach city N.
Example
Assume that N = 3 M = 1, K = 1. c = [2,4]
Bridges
• 1 3 5
The cost of going from 1 to 3 using connections is 6. or we can use 1 bridge and go from 1 to 3 using costs. There the
answer is 5
Function description
function provided in the editor This function takes the following
Answers
Answer: using dp
Explanation:
public class Sample {
public static void main(String[] args) {
int n = 5;
int m = 3;
int k = 1;
int[] cost = {1, 2, 1, 4};
int[][] bridges = new int[n+1][n+1];
bridges[1][2] = 1;
bridges[1][3] = 2;
bridges[3][4] = 1;
int[] ps = new int[n+1];
ps[0] = 0; ps[1] = 0;
for (int i=2; i<=n; i++) {
ps[i] = cost[i-2] + ps[i-1];
}
int ans = solve(1, n, cost, ps, bridges, k, 0);
System.out.println(ans);
}
public static int solve(int s, int d, int[] cost, int[] ps, int[][] bridges, int k, int count) {
if (s == d) {
return 0;
}
if ((s+1) == d) {
if (bridges[s][d] != 0 && count < k) {
return Math.min(bridges[s][d], cost[s-1]);
}
return cost[s-1];
}
int min = Integer.MAX_VALUE;
int c1, c2;
for (int i=s+1; i<=d; i++) {
c1 = ps[i] - ps[s];
c1 = c1 + solve(i, d, cost, ps, bridges, k, count);
if (count < k && bridges[s][i] != 0) {
c2 = bridges[s][i] + solve(i, d, cost, ps, bridges, k, count+1);
c1 = Math.min(c1, c2);
}
min = Math.min(min, c1);
}
return min;
}
}
Answer:
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] input = reader.readLine().trim().split(" ");
int N = Integer.valueOf(input[0]);
int M = Integer.valueOf(input[1]);
int K = Integer.valueOf(input[2]);
// System.out.println(String.format("N = %d, M = %d, K = %d", N, M, K));
int[] road_cost = Arrays.asList(reader.readLine().trim().split(" ")).stream().mapToInt(Integer::parseInt)
.toArray();
// for (int c : road_cost) {
// System.out.print(c + " ");
// }
Map<String, Integer> bridges = new HashMap<>();
for (int i = 0; i < M; i++) {
int[] br_input = Arrays.asList(reader.readLine().trim().split(" ")).stream().mapToInt(Integer:: parseInt).toArray();
bridges.put(String.format("%d_%d", br_input[0]-1, br_input[1]-1), br_input[2]);
}
int total_cost = 0;
for (int i = 0; i < N - 1; i++) {
total_cost += road_cost[i];
}
// System.out.println("road cost is " + total_cost);
ArrayList<Integer> c = new ArrayList<>();
for (Map.Entry<String, Integer> bridge : bridges.entrySet()) {
int[] vertices = Arrays.asList(bridge.getKey().split("_")).stream().mapToInt(Integer::parseInt).toArray();
c.add(getDiff(vertices, bridge.getValue(), road_cost));
}
Collections.sort(c, Collections.reverseOrder());
int [] cc = c.stream().mapToInt(i->i).toArray();
for (int i = 0; i < K; i++) {
// System.out.println("subtracting "+cc[i]+"from total_cost");
if(cc[i]>0)
total_cost = total_cost - cc[i];
}
System.out.println(total_cost);
}
public static int getDiff(int[] vertices, int bridgeCost, int[] roadCost) {
int node1 = vertices[0];
int node2 = vertices[1];
int c = 0;
for (int i : Arrays.copyOfRange(roadCost, node1, node2)) {
c+=i;
}
return c-bridgeCost;
}
Explanation: