3543. Maximum Weighted K-Edge Path

Problem

BFS: TLE

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

DFS : TLE

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

dp with memoization: works

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