1. 原題： https://www.patest.cn/contests/pat-a-PRactise/1053

2. 思路：

3. 源碼（已AC）：

#include<iostream>#include<algorithm>//使用sort函數#include<vector>using namespace std;vector<int> pwt;//存儲路徑的每個結點權值vector<int> nwt;//存儲樹的每個結點權值int N, M, S;//分別為總結點數， 非葉子節點數，給出的權值struct Node{	bool Operator<(const Node &b) const//重載比較運算符	{		return wgt > b.wgt;	}	int id;//結點編號	int wgt;//權值};vector< vector<Node> > vtree;//類似圖的鄰接表表示，嵌套vector，表示結點的孩子void dfs(int s, int sum);//dfs，參數為遍歷起點，累計的權值int main(void){	//freopen("in.txt", "r", stdin);	cin >> N >> M >> S;	nwt.resize(N);//重新定義數組大小	vtree.resize(N);	for (int i = 0; i < N; i++)//保存每個結點權值		cin >> nwt[i];	for (int i = 0; i < M; i++ )	{		int par, num;		cin >> par >> num;		vtree[par].resize(num);		for (int j = 0; j < num; j++)//每個孩子結點壓入父結點的數組中		{			Node tem;			cin >> tem.id;			tem.wgt = nwt[tem.id];			vtree[par][j] = tem;		}		sort(vtree[par].begin(), vtree[par].end());//降序排序	}		dfs(0, 0);	return 0;}void dfs(int s, int sum){	sum += nwt[s];	pwt.push_back(nwt[s]);	if (sum > S)//大于直接返回上一級		return;	if (sum == S && vtree[s].empty())//相等且為葉子結點，為所求，輸出結果	{		for (int i = 0; i < pwt.size(); i++)		{			if (i == 0)				cout << pwt[i];			else				cout << ' ' << pwt[i];		}		cout << endl;		return;	}	if (sum < S && vtree[s].size() > 0)//小于的話，繼續dfs	{		for (int i = 0; i < vtree[s].size(); i++)		{			dfs(vtree[s][i].id, sum);			pwt.pop_back();//從dfs里返回后要彈出最后壓入的		}	}	return;}