洛谷P1073 [NOIP2009 提高組] 最優貿易（分層圖+最短路）

題意：

帶點權的有向圖，每個點的點權表示，在該點購買或者賣出水晶球的價格。求從1到n，選擇在一點購買水晶球，再選擇在一點賣出水晶球後的最大收益。一個點可以多次經過。

思路：

方法一：縮點+dp（拓撲排序）

方法二：分層圖+最短路：

圖檔來源

每層邊權為0，連接配接第一層的點到第二層的點的權值為點權的負數，表示在該點購買，連接配接第二層的點到第三層的點的權值為點權的正數，表示在該點賣出

因為有負權，隻能跑spfa