P1073 最优贸易

题目注意事项

算法分析

1. 　　建立正图E1，反图E2
2. 　　SPFA1求解从1出发到达每个点的路径上价格最小值Min[]，到达不了则Min[]=∞
3. 　　SPFA2求解从N出发到达每个点的路径上价格最大值Max[]，到达不了则Max[]=0
4. 　　枚举每个点计算差值Max[i]-Min[i]，最大差值即为答案（Min[i]！=∞&&Max[i]！=0）

证明

1. 因为我们正向的跑了一边spfa更新最小值就相当于把起点到每个点的最小值求出来了
2. 然后我第二遍spfa就做了两件事情第一个证明了连通性【因为我这个题目中有一些路是单向的，所以说可能某些点买的价格特别低或者特别高，但是我去的那儿是陷阱，你进去了就出不来了这样你的答案就是错的了，所以我把图反过来建这样你从终点可以反着跑到这个点也就代表这个点可以正着跑到终点，这就相当于证明了连通性】
3. 以此保证最小买入点在最大卖出点前