Deloitte | COGNIZANT | IBM | CAPGEMINI
import java.util.*;
public class TestClass {
static class Edge {
int to, cost;
Edge(int to, int cost) {
this.to = to;
this.cost = cost;
}
}
static List<List<Edge>> graph;
static List<Integer> bestPath = new ArrayList<>();
static int maxVisitLength = 0;
public static void optimalPath(int N, int M, int price, int[] source, int[] dest, int[] weight) {
graph = new ArrayList<>();
for (int i = 0; i <= N; i++) graph.add(new ArrayList<>());
for (int i = 0; i < M; i++) {
int u = source[i];
int v = dest[i];
int w = weight[i];
graph.get(u).add(new Edge(v, w));
graph.get(v).add(new Edge(u, w));
}
boolean[] visited = new boolean[N + 1];
List<Integer> path = new ArrayList<>();
path.add(1);
visited[1] = true;
dfs(1, price, 0, visited, path);
for (int val : bestPath) {
System.out.print(val + " ");
}
}
static void dfs(int node, int budget, int costSoFar, boolean[] visited, List<Integer> path) {
int returnCost = costSoFar;
if (2 * returnCost <= budget) {
if (path.size() > maxVisitLength) {
maxVisitLength = path.size();
bestPath = new ArrayList<>(path);
for (int i = path.size() - 2; i >= 0; i--) {
bestPath.add(path.get(i));
}
}
} else {
return;
}
for (Edge edge : graph.get(node)) {
if (!visited[edge.to]) {
int newCost = costSoFar + edge.cost;
if (2 * newCost <= budget) {
visited[edge.to] = true;
path.add(edge.to);
dfs(edge.to, budget, newCost, visited, path);
path.remove(path.size() - 1);
visited[edge.to] = false;
}
6 · 2.3K ·