[PAT-A] 1053 Path of Equal Weight

Java

import java.util.*;

public class Main {
    static final int N = 110;
    static int n, m, S;
    static boolean[][] g = new boolean[N][N];
    static int[] w = new int[N];
    static List<List<Integer>> ans = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();
        S = scanner.nextInt();

        for (int i = 0; i < n; ++i) {
            w[i] = scanner.nextInt();
        }

        for (int i = 0; i < m; ++i) {
            int id = scanner.nextInt();
            int k = scanner.nextInt();

            for (int j = 0; j < k; ++j) {
                int son = scanner.nextInt();
                g[id][son] = true;
            }
        }

        List<Integer> path = new ArrayList<>();
        path.add(w[0]);
        dfs(0, w[0], path);

        ans.sort((a, b) -> {
            for (int i = 0; i < Math.min(a.size(), b.size()); ++i) {
                if (!a.get(i).equals(b.get(i))) {
                    return b.get(i) - a.get(i);
                }
            }
            return b.size() - a.size();
        });

        for (List<Integer> p : ans) {
            for (int i = 0; i < p.size(); ++i) {
                if (i > 0) System.out.print(" ");
                System.out.print(p.get(i));
            }
            System.out.println();
        }

        scanner.close();
    }

    static void dfs(int u, int s, List<Integer> path) {
        boolean isLeaf = true;
        for (int i = 0; i < n; ++i) {
            if (g[u][i]) {
                isLeaf = false;
                break;
            }
        }

        if (isLeaf) {
            if (s == S) ans.add(new ArrayList<>(path));
        } else {
            for (int i = 0; i < n; ++i) {
                if (g[u][i]) {
                    path.add(w[i]);
                    dfs(i, s + w[i], path);
                    path.remove(path.size() - 1);
                }
            }
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 110;

int n, m, S;
bool g[N][N];
int w[N];
vector <vector<int>> ans;

void dfs(int u, int s, vector<int> &path) {
    bool is_leaf = true;
    for (int i = 0; i < n; ++i)
        if (g[u][i]) {
            is_leaf = false;
            break;
        }

    if (is_leaf) {
        if (s == S) ans.push_back(path);
    } else {
        for (int i = 0; i < n; ++i)
            if (g[u][i]) {
                path.push_back(w[i]);
                dfs(i, s + w[i], path);
                path.pop_back();
            }
    }
}

int main() {
    cin >> n >> m >> S;
    for (int i = 0; i < n; ++i) cin >> w[i];

    for (int i = 0; i < m; ++i) {
        int id, k;
        cin >> id >> k;

        while (k--) {
            int son;
            cin >> son;
            g[id][son] = true;
        }
    }

    vector<int> path({w[0]});
    dfs(0, w[0], path);

    sort(ans.begin(), ans.end(), greater < vector < int > > ());

    for (auto p: ans) {
        for (int i = 0; i < p.size(); ++i) {
            if (i > 0) cout << " ";
            cout << p[i];
        }
        cout << endl;
    }

    return 0;
}