想象一个完整的无向加权边图，其中每个边都有2个权重：金钱和能量（可以是正数或负数）。您从一定的能量开始，没有钱。到达节点后，您将从权重中获得/失去金钱和精力。目标是在用尽能量之前收集尽可能多的钱。
我可以使用哪种算法在整个图中找到最佳路径？我正在考虑先对整个图形进行预处理，然后再走上获得最多金钱却减少能量损失的道路。
对于有向无环图，您可以执行以下操作：
对节点进行拓扑排序，然后还原边缘或构造一个数据结构，该结构告诉您所有具有指向给定节点的边缘的节点以及到达该节点所需的金钱/能量。
在每个节点中，您存储了一组由能量，金钱，上一个元组和当前节点组成的元组（后两个用于重建最佳路径）。首先，您只需将具有初始能量和金钱的元组添加到起始节点（先前的元组为null）。
对于起始节点之后的每个节点，请执行以下操作，同时跟踪具有最高货币值的元组：对于此类节点构造的所有元组，遍历可以从其到达当前节点的所有节点。当前节点的元组：
如果金钱或能量变为负数，或者当前节点已经包含具有大于或等于刚构造的元组的金钱和能量值的元组，则不执行任何操作。
否则将元组添加到当前节点，并删除具有较小或相等的能量和货币值的当前节点的所有元组（这可以在步骤1中完成，因此您只需要遍历元组一次而不是两次）。
使用沿途找到的具有最高货币值的元组重建路径。