所附图表以特定方式直观地显示数据，显示了一个为每个节点分配值的金字塔，以及指示遍历金字塔以累积点所需路径的箭头。当一个人穿过金字塔时，他们会收集他们经过的节点中的值。我想知道通过遍历这些节点可以获得的最大值是多少。我将数据作为整数流，或者如果您愿意，可以将输入视为整数数组。因此，在图中绘制的示例中，您的输入是40、-10、25、75、-30、-5、-15、20、120、100。第一个元素填充金字塔顶部的节点。第二个元素占据金字塔第二行中最左边的节点。元素在金字塔周围蜿蜒，从左到右排列成行。输入保证完成一个金字塔。
积分累积规则：每个路径只能对节点中的值计数一次从每个节点，您可以到达两个节点，除非您到达了一个没有叶子的节点，指示路径的结束。图形的图像
您可以将值从节点移动到传入边。
如果将值(*(-1((的符号反转，则可以简单地在每个最终节点上应用Bellman-Ford算法来寻找最短路径。Dijkstra不会工作，因为存在负边。取你能得到的最低结果。
最短路径的结果需要再次反转。最后，我们丢失了金字塔顶端的值(没有传入节点(。我们需要将此值添加到该值上，并且应该得到答案。
这不是一个最优解，但它将在O(sqrt(|V|(|V||E|(内运行