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

2. 思路：

3. 源碼（已AC）：

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