洛谷P1073 [NOIP2009 提高组] 最优贸易（分层图+最短路）

题意：

带点权的有向图，每个点的点权表示，在该点购买或者卖出水晶球的价格。求从1到n，选择在一点购买水晶球，再选择在一点卖出水晶球后的最大收益。一个点可以多次经过。

思路：

方法一：缩点+dp（拓扑排序）

方法二：分层图+最短路：

图片来源

每层边权为0，连接第一层的点到第二层的点的权值为点权的负数，表示在该点购买，连接第二层的点到第三层的点的权值为点权的正数，表示在该点卖出

因为有负权，只能跑spfa