PAT甲級-1053 Path of Equal Weight (30分)

題目：1053 Path of Equal Weight (30分)

分析：排序題，這裡輸出的時候直接sort，沒有寫cmp函數，則從尾部開始輸出，或者也可以在輸入的時候對每個節點的孩子進行sort（很多部落格都是這樣寫的，代碼都一樣，但還是要根據自己的思路來比較好）

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
#define MAX 999999999
using namespace std;
int n,m,k;
struct node{
    int id,weight;
    vector<int>child;
};
node node[101];
int visi[101];
int dis;
vector<int>temp;
vector<vector<int>>ans;
void dfs(int root)
{
    visi[root] = 1;
    if(node[root].child.size() == 0 && dis == k)
        ans.push_back(temp);
    for(int i = 0;i<node[root].child.size();i++)
    {
        if(!visi[node[root].child[i]])
        {
            dis += node[node[root].child[i]].weight;
            temp.push_back(node[node[root].child[i]].weight);
            dfs(node[root].child[i]);
            dis -= node[node[root].child[i]].weight;
            temp.pop_back();
        }
    }
    visi[root] = 0;
}
int main()
{
    cin>>n>>m>>k;
    for(int i = 0;i<n;i++)
    {
          node[i].id = i;
          cin>>node[i].weight;
    }
    for(int i = 0;i<m;i++)
    {
        int id,num;
        cin>>id>>num;
        for(int j = 0;j<num;j++)
        {
            int x;
            cin>>x;
            node[id].child.push_back(x);
        }
    }
    dis = node[0].weight;
    temp.push_back(node[0].weight);
    dfs(0);
    sort(ans.begin(),ans.end(),cmp);
    for(int i = ans.size() - 1;i >= 0;i--)
    {
        for(int j = 0;j<ans[i].size();j++)
            if(j != ans[i].size() - 1)
                cout<<ans[i][j]<<" ";
            else
                cout<<ans[i][j]<<endl;
    }
    return 0;
}