#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm> using namespace std; vector<vector<int>* > paths; class Node {
public:
vector<int> child;
int weight;
Node(int w = ) : weight(w){}
}; int str2num(const char* str) {
if (str == NULL) return ;
int v = ;
int i = ;
char ch;
while ((ch = str[i++]) != '\0') {
v = v * + (ch - '');
}
return v;
} void print_nodes(vector<Node> &nodes) {
for (int i=; i<nodes.size(); i++) {
printf("id:%d nchild:%d\n", i, nodes[i].child.size());
for (int j=; j<nodes[i].child.size(); j++) {
printf(" %d", nodes[i].child[j]);
}
printf("\n");
}
} void dfs(vector<Node> &nodes, vector<int> &path, int idx, int sum, int target) {
if (idx >= nodes.size()) return; // invalid case;
int path_weight = sum + nodes[idx].weight;
if (path_weight == target) {
// not a leaf node, ignore it
if (!nodes[idx].child.empty()) {
return;
}
// leaf node, so we got a Root->Leaf path weight equal to the target weight
path.push_back(nodes[idx].weight);
// record it
paths.push_back(new vector<int>(path));
path.pop_back();
return;
} else if (path_weight > target) {
// impossible continue to find a valid path
return;
} int clen = nodes[idx].child.size();
for (int i=; i<clen; i++) {
path.push_back(nodes[idx].weight);
dfs(nodes, path, nodes[idx].child[i], path_weight, target);
path.pop_back();
} }
class cmpcls {
private:
vector<Node>* nodes;
public:
cmpcls(vector<Node>* ns) : nodes(ns) {}
bool operator()(int a, int b) {
if ((*nodes)[a].weight > (*nodes)[b].weight) {
return true;
} else {
return false;
}
}
}; bool mycmp(const vector<int>* a, const vector<int>* b) {
int len = ;
if (a->size() > b->size()) {
len = b->size();
} else {
len = a->size();
}
for (int i=; i<len; i++) {
if ((*a)[i] > (*b)[i]) return true;
}
return false;
} void print_path() {
int len = paths.size();
for (int i=; i<len; i++) {
int plen = paths[i]->size();
printf("%d", (*paths[i])[]);
for (int j=; j<plen; j++) {
printf(" %d", (*paths[i])[j]);
}
printf("\n");
}
}
int main() {
int N, M, S; scanf("%d%d%d", &N, &M, &S);
vector<Node> nodes(N); char buf[]; for (int i=; i<N; i++) {
int w = ;
scanf("%d", &w);
nodes[i].weight = w;
}
cmpcls cmpobj(&nodes); for (int i=; i<M; i++) {
int nchild = ;
scanf("%s%d", buf, &nchild);
Node& node = nodes[str2num(buf)];
for (int j=; j<nchild; j++) {
scanf("%s", buf);
node.child.push_back(str2num(buf));
}
sort(node.child.begin(), node.child.end(), cmpobj);
}
vector<int> path;
dfs(nodes, path, , , S);
print_path();
return ;
}
原先写的比较函数有问题一直有个case不对,换个思路直接把childnode的顺序按照weight大小来排,这样最终的结果就是按照规定排序。