AcWing 341：最优贸易题解视频（最短路与动态规划）

AcWing 341. 最优贸易
解题思路：首先考虑动态规划的思路，将n个点看作是n个状态的划分节点，其中dp[k]表示以k作为划分节点，在k之前进行买入操作，在k之后完成卖出操作。在这一过程中，虽然n个状态之间可能存在重复的情况，但可以确保不会遗漏任何可能的状态（这符合动态规划用于求最值的基本条件）。接下来的关键在于如何计算这n个状态对应的dp值。由于图中可能存在环路，因此无法直接采用常规的状态转移方式来求解动态规划问题，转而使用spfa算法来计算最短路径。不过此时权值的计算方式从边转移到了点上，但其核心原理保持一致。需要分别计算两种最短路径：一种是能够到达某一点x的最低买入价格，通过遍历由ht所记录的邻接表中的正向边来获取；另一种是能够到达某一点x的最高卖出价格，通过遍历由hs记录的逆向邻接表来获取。在得到每个节点对应的这两个数值后，将其相加即可得到相应的dp值。最终通过遍历所有dp值找到其中的最大值作为问题的答案

    #include<bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1e5 + 10, M = 2e6 + 10;
    
    int ht[N], hs[N]