3543. Maximum Weighted K-Edge Path

class Solution { public int maxWeight(int n, int[][] edges, int k, int t) { if (k > n) return -1; List<List<Edge>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int edge[] : edges) { Edge e = new Edge(edge[1], edge[2]); adj.get(edge[0]).add(e); } int maxSum = -1; for (int i = 0; i < n; i++) { maxSum = Math.max(maxSum, bfs(i, adj, t, k)); } return maxSum; } public int bfs(int node, List<List<Edge>> adj, int T, int k) { Queue<Tuple> q = new LinkedList<>(); q.add(new Tuple(node, 0, 0));// current node, cost to reach current node, and no of edges so far int max = -1; while (!q.isEmpty()) { Tuple t = q.remove(); if (t.d < T && t.e == k) { max = Math.max(max, t.d); } for (Edge e : adj.get(t.n)) { int sum = t.d + e.c; int noOfEdgesSoFar = t.e + 1; if (sum < T && noOfEdgesSoFar <= k) { if (noOfEdgesSoFar == k) { max = Math.max(max, sum); } else { q.add(new Tuple(e.n, sum, noOfEdgesSoFar)); } } } } return max; } } class Edge { int n; int c; public Edge(int n, int c) { this.n = n; this.c = c; } } class Tuple { int n; int d; int e; public Tuple(int n, int d, int e) { this.n = n; this.d = d; this.e = e; } } 

class Solution { public int maxWeight(int n, int[][] edges, int k, int t) { if(k>n) return -1; List<List<Edge>> adj = new ArrayList<>(); for(int i =0;i<n;i++) adj.add(new ArrayList<>()); for(int edge[] : edges){ Edge e = new Edge(edge[1], edge[2]); adj.get(edge[0]).add(e); } int maxSum = -1; for(int i =0;i<n;i++){ maxSum = Math.max(maxSum,dfs(new Tuple(i,0,0),adj,t, k)); } return maxSum; } public int dfs(Tuple t, List<List<Edge>> adj, int T, int k){ if(t.e == k){ if(t.d < T) return t.d; return -1; } int max = -1; for(Edge e : adj.get(t.n)){ int sum = t.d + e.c; int noOfEdgesSoFar = t.e + 1; if(sum<T && noOfEdgesSoFar<=k){ max = Math.max(max, dfs(new Tuple(e.n, sum, noOfEdgesSoFar), adj, T, k)); } } return max; } } class Edge{ int n;//to node int c;//edge weight public Edge(int n ,int c){ this.n = n; this.c =c; } } class Tuple{ int n;//node int d;//cost so far int e;//noOfEdgesSoFar public Tuple(int n ,int d, int e){ this.n = n; this.d = d; this.e = e; } } 

class Solution { public int maxWeight(int n, int[][] edges, int k, int t) { if(k>n) return -1; List<List<Edge>> adj = new ArrayList<>(); for(int i =0;i<n;i++) adj.add(new ArrayList<>()); for(int edge[] : edges){ Edge e = new Edge(edge[1], edge[2]); adj.get(edge[0]).add(e); } int maxSum = -1; Map<Tuple,Integer> dp = new HashMap<>(); for(int i =0;i<n;i++){ maxSum = Math.max(maxSum,dfs(new Tuple(i,0,0),adj,t, k,dp)); } return maxSum; } public int dfs(Tuple t, List<List<Edge>> adj, int T, int k,Map<Tuple,Integer> map){ if(t.e == k){ if(t.d < T) return t.d; return -1; } if(map.containsKey(t)) return map.get(t); int max = -1; for(Edge e : adj.get(t.n)){ int sum = t.d + e.c; int noOfEdgesSoFar = t.e + 1; if(sum<T && noOfEdgesSoFar<=k){ max = Math.max(max, dfs(new Tuple(e.n, sum, noOfEdgesSoFar), adj, T, k,map)); } } map.put(t, max); return map.get(t); } } class Edge{ int n; int c; public Edge(int n ,int c){ this.n = n; this.c =c; } } class Tuple{ int n; int d; int e; public Tuple(int n ,int d, int e){ this.n = n; this.d = d; this.e = e; } @Override public boolean equals(Object o){ if(o ==null) return false; if(o== this) return true; if(o.getClass()!= this.getClass()) return false; Tuple t = (Tuple) o; if(t.n != this.n || t.d != this.d || t.e != this.e) return false; return true; } @Override public int hashCode(){ return Arrays.hashCode(new int[]{this.n, this.d, this.e}); } }