Routes with an exact total weight

def count_target_paths(n, edges, source, destination, target):
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    on_path = [False] * n

    def explore(u, total):
        if u == destination:
            return 1 if total == target else 0     # never continue past the destination
        on_path[u] = True
        count = 0
        for v, w in adj[u]:
            if not on_path[v]:
                count += explore(v, total + w)
        on_path[u] = False                         # backtrack
        return count

    return explore(source, 0)

#include <functional>
#include <utility>
#include <vector>

long long solve(int n, const std::vector<std::vector<int>>& edges, int source, int destination, int target) {
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    for (const auto& e : edges) adj[e[0]].push_back({e[1], e[2]});
    std::vector<bool> onPath(n, false);
    std::function<long long(int, int)> explore = [&](int u, int total) -> long long {
        if (u == destination) return total == target ? 1 : 0;   // stop at the destination
        onPath[u] = true;
        long long count = 0;
        for (auto [v, w] : adj[u])
            if (!onPath[v]) count += explore(v, total + w);
        onPath[u] = false;                                        // backtrack
        return count;
    };
    return explore(source, 0);
}

import java.util.*;

class Solution {
    private List<List<int[]>> adj;
    private boolean[] onPath;
    private int destination, target;

    public long countTargetPaths(int n, int[][] edges, int source, int destination, int target) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e[2]});
        onPath = new boolean[n];
        this.destination = destination;
        this.target = target;
        return explore(source, 0);
    }

    private long explore(int u, int total) {
        if (u == destination) return total == target ? 1 : 0;    // stop at the destination
        onPath[u] = true;
        long count = 0;
        for (int[] e : adj.get(u))
            if (!onPath[e[0]]) count += explore(e[0], total + e[1]);
        onPath[u] = false;                                         // backtrack
        return count;
    }
}

function countTargetPaths(n, edges, source, destination, target) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u].push([v, w]);
  const onPath = new Array(n).fill(false);
  const explore = (u, total) => {
    if (u === destination) return total === target ? 1 : 0;   // stop at the destination
    onPath[u] = true;
    let count = 0;
    for (const [v, w] of adj[u]) if (!onPath[v]) count += explore(v, total + w);
    onPath[u] = false;                                         // backtrack
    return count;
  };
  return explore(source, 0);
}

fn solve(n: i64, edges: &[[i64; 3]], source: i64, destination: i64, target: i64) -> i64 {
    let n = n as usize;
    let mut adj = vec![Vec::new(); n];
    for e in edges {
        adj[e[0] as usize].push((e[1] as usize, e[2]));
    }
    fn explore(u: usize, total: i64, dest: usize, target: i64, adj: &[Vec<(usize, i64)>], on_path: &mut Vec<bool>) -> i64 {
        if u == dest {
            return if total == target { 1 } else { 0 };   // stop at the destination
        }
        on_path[u] = true;
        let mut count = 0;
        for &(v, w) in &adj[u] {
            if !on_path[v] {
                count += explore(v, total + w, dest, target, adj, on_path);
            }
        }
        on_path[u] = false;                                // backtrack
        count
    }
    let mut on_path = vec![false; n];
    explore(source as usize, 0, destination as usize, target, &adj, &mut on_path)
}

import qualified Data.Map.Strict as M
import qualified Data.Set as S

solve :: Int -> [[Int]] -> Int -> Int -> Int -> Int
solve _ edges source dest target = explore source 0 S.empty
  where
    adj = M.fromListWith (++) [(u, [(v, w)]) | [u, v, w] <- edges]
    explore u total onPath
      | u == dest = if total == target then 1 else 0      -- stop at the destination
      | otherwise = sum [ explore v (total + w) onPath'
                        | (v, w) <- M.findWithDefault [] u adj, not (S.member v onPath') ]
      where onPath' = S.insert u onPath