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; }