17.[NOIP2009 提高组] 最优贸易 难度：普及+/提高 来源：-- AC代码（C++/C#）： 没有注释，自行学习。 by：yanghaozhe Tips： 代码中的： 实际是指： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 你的点赞和关注就是我更新题解的最大动力！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ -----------------------------点个赞吧 ↓ ！-----------------------------

SPFA算法，第v[i]点为从1到i一路上最小值，t[i]表示从i到n的最大值

(SPFA) O(n+/km) 先求出：从 1 走到 i 的过程中，买入水晶球的最低价格 dmin[i]； 从 i 走到 n的过程中，卖出水晶球的最高价格 dmax[i]； 然后枚举每个城市作为买卖的中间城市，求出 dmax[i] - dmin[i] 的最大值即可。

AC代码 欢迎加入团队

题意分析 求出一点到终点 nnn 的所有路径上最大值和起点 111 到该点的所有路径上最小值的差值的最大值。 解题思路 先从简单的链看： 看起来似乎和最短路关系不大，但实际上，这些最小值和最大值都需要最短路来维护。让 SPFASPFASPFA 从点 111 出发，在去点 nnn 的过程中不断更新到每个点的最小值，切记不能搜到 nnn 就停止，这样可能错过最优解。同理，从点 nnn 出发再跑一遍，但维护的是到 nnn 最大值。 DijkstraDijkstraDijkstra 无法判断先走哪条，Bellman−FordBellman-FordBellman−Ford 时间复杂度 O(n×m)O(n \times m)O(n×m) 必定超时，只能用 SPFASPFASPFA。有点像广搜，但 SPFASPFASPFA 本就很像广搜。 AC代码 时间复杂度 O(km)O(km)O(km)，kkk是小常数，最坏情况 O(nm)O(nm)O(nm)，会超时，但本题没有这种毒瘤数据，而且可以写 LLLLLLLLL 优化(虽然不能说效果好吧)。