/1053 Path of Equal Weight 算法下P311 天勤

//1053 Path of Equal Weight  算法下P311 天勤
#include <algorithm>
#include <iostream>
#define maxSize 110
using namespace std;
struct TNode{
    int weight;
    int children[maxSize];
    int n; //可用vector实现  省略n
};
TNode nodes[maxSize];
bool cmp(int a,int b){
    return nodes[a].weight > nodes[b].weight;
}
int N,M,S;
int path[maxSize];
void DFS(int index,int numNode,int sum){

    if(sum > S) return;
    if(sum == S){


        if(nodes[index].n != 0) return;
        for(int i=0;i<numNode;++i){
            cout<<nodes[path[i]].weight;
            if(i < numNode - 1) cout<<" ";
            else cout<<endl;
        }
        return;
    }
    for(int i=0;i<nodes[index].n;++i){
        int temp = nodes[index].children[i];
        path[numNode] = temp;
        DFS(temp,numNode+1,sum+nodes[temp].weight);
    }
}

int main(){
    cin >> N >> M >>S;
    for(int i=0;i<N;++i){
        cin>>nodes[i].weight;
        nodes[i].n = 0;
    }

    int ID,K,child;
    for(int i=0;i<M;++i){
        cin>>ID>>K;
        for(int j=0;j<K;++j){
            cin>>child;
            nodes[ID].children[nodes[ID].n++] = child;
        }
        sort(nodes[ID].children,nodes[ID].children+nodes[ID].n,cmp);
    }
    DFS(0,1,nodes[0].weight);
    return 0;
}