首页 > 代码库 > PAT 1053 Path of Equal Weight
PAT 1053 Path of Equal Weight
#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 = 0) : weight(w){}};int str2num(const char* str) { if (str == NULL) return 0; int v = 0; int i = 0; char ch; while ((ch = str[i++]) != ‘\0‘) { v = v * 10 + (ch - ‘0‘); } return v;}void print_nodes(vector<Node> &nodes) { for (int i=0; i<nodes.size(); i++) { printf("id:%d nchild:%d\n", i, nodes[i].child.size()); for (int j=0; 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=0; 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 = 0; if (a->size() > b->size()) { len = b->size(); } else { len = a->size(); } for (int i=0; i<len; i++) { if ((*a)[i] > (*b)[i]) return true; } return false;}void print_path() { int len = paths.size(); for (int i=0; i<len; i++) { int plen = paths[i]->size(); printf("%d", (*paths[i])[0]); for (int j=1; 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[4]; for (int i=0; i<N; i++) { int w = 0; scanf("%d", &w); nodes[i].weight = w; } cmpcls cmpobj(&nodes); for (int i=0; i<M; i++) { int nchild = 0; scanf("%s%d", buf, &nchild); Node& node = nodes[str2num(buf)]; for (int j=0; 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, 0, 0, S); print_path(); return 0;}
原先写的比较函数有问题一直有个case不对,换个思路直接把childnode的顺序按照weight大小来排,这样最终的结果就是按照规定排序。
PAT 1053 Path of Equal Weight
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。