算法
(SPFA) O(n+km)
先求出：
- 从 1 走到 i 的过程中，买入水晶球的最低价格
dmin[i]； - 从 i 走到 n 的过程中，卖出水晶球的最高价格
dmax[i]；
然后枚举每个城市作为买卖的中间城市，求出 dmax[i] - dmin[i] 的最大值即可。
求 dmin[i] 和 dmax[i] 时，由于不是拓扑图，状态的更新可能存在环，因此不能使用动态规划，只能使用求最短路的方式。
另外，我们考虑能否使用 dijkstra 算法，如果当前 dmin[i] 最小的点是 5，那么有可能存在边 5-> 6, 6-> 7, 7-> 5，假设当前 dmin[5] = 10，则有可能存在 6 的价格是11， 但 7 的价格是3，那么 dmin[5] 的值就应该被更新成3，因此当前最小值也不一定是最终最小值，所以dijkstra算法并不适用，我们只能采用 spfa 算法。
时间复杂度
瓶颈是SPFA，SPFA 算法的时间复杂度是 O(km)，其中 k 一般情况下是个很小的常数，最坏情况下是 n, n 表示总点数，m 表示总边数。因此总时间复杂度是 O(km)。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 2000010;
int n, m;
int price[N];
int h[N], rh[N], e[M], ne[M], idx;
int dmin[N], dmax[N];
bool st[N];
void add(int *h, int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void spfa(int *d, int start, int *h, bool flag)
{
queue<int> q;
memset(st, 0, sizeof st);
if (flag) memset(d, 0x3f, sizeof dmin);
q.push(start);
st[start] = true;
d[start] = price[start];
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (flag && d[j] > min(d[t], price[j]) || !flag && d[j] < max(d[t], price[j]))
{
if (flag) d[j] = min(d[t], price[j]);
else d[j] = max(d[t], price[j]);
if (!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
for (int i = 1; i <= n; i ++ ) scanf("%d", &price[i]);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(h, a, b), add(rh, b, a);
if (c == 2) add(h, b, a), add(rh, a, b);
}
spfa(dmin, 1, h, true);
spfa(dmax, n, rh, false);
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, dmax[i] - dmin[i]);
printf("%d\n", res);
return 0;
}
最一般的最短路维护的是路径上的sum性质，本题维护的是max和min性质，sum性质具有累加性（就是要从前面的值基础上累加，后续出现只会越来越大，所以第一次出现的就是最短），而max 和min对于新出现的数，单独比较即可，所以不能用dijkstra（dijkstra就是利用的sum的累加性）
总的来说就是max和min，后面出现的数不一定比前面的数都差（而dijkstra的sum性质能保证后面出现的数都比前面的数都差）
感谢！太透彻了
%%%
透彻！！！
前面的那道题里的高赞代码就是用dijkstra维护了路径中的最值，这个不冲突，因为max和min指的是在之前走过的路径中的最大最小值，对于前面来说就是固定的，不影响，这题之所以不能用dijkstra是因为可能存在环（可以重复经过一个点）。
要使用dijkstra的前提条件是明确知道起点一定是最短的，因为基于贪心的策略，每次都是使用距离最短的点去更新其他的点，如果不能保证起点是最短的就不能用，这样想对吗？
对，出去跑几圈到达最便宜的点又回到起点，这时起点就会又变小，所以鬼知道起点是不是最小，而且扩展的点也不知道以后会不会变小
主要是环的存在再加上这个权值的定义是路径某一点的值这两个性质导致的
666666
不是的吧，这题之所以不能用dijkstra算法，是因为可能存在环，正常最短路问题每个点经过后会标记，不会多次访问，所以每个点最多经过一次，但这道题允许重复经过点。dijkstra有点类似于动态规划，由前面推后面，自底向上，后面的状态不可以影响到前面的状态。
谁能教教反向图的意义，看不懂反向图是干嘛的
正向图的意义是求出所有从城市1出发到所有点的最小成本，反向图的意义是求出从城市n到所有城市的最大价格，这样才能方便枚举每个城市的时候，提前得到从1到该城市的最小成本，以及从该城市到城市n的最大价格，从而赚取最大的利润。
感觉反向图的意义是保证这个点是能到达n点的成本最大值
其实原图就是求出 1 - k 的 前k个城市选择一个城市买入的最小代价。
反向图是求出n - k ， 后n - k 个城市选择一个城市卖出的最大收益。
为什么要建这个返图呢？因为假设你选择 k 这个城市买入，那么你一定只能选择k之后的城市卖出。找到后面在哪个城市卖出受益最大 ，其实你只需要从n出发，到n - k 后面这些城市中选择一个城市受益最大的城市卖出即可。
提醒您注意一下，dmin 和dmax 的含义，脑中模拟一下。
用
spfa见解：因为dijkstra中的点只会进去一次，而不会再进去第二次（主要是由于st[]只标记为true，而没有被标记回false），而spfa可以把一个点加入队列多次，所以上面那个例子中dmin[5]就会再次进队把dmin[6]更新，故只能用spfa。PS:实际上，上面说的spfa和dijksta的差别也是为什么用spfa判断图中是否有环，而不用后者原因谁说不能用
Dijkstra?我就偏用,SPFA已死，不再怀念#include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; const int INF = 0x3f3f3f3f; const int N = 100010, M = 2000010; int n, m; int dist1[N], dist2[N]; // 正反建图，传入头数组指针 int h1[N], h2[N], e[M], ne[M], w[M], idx; void add(int *h, int a, int b, int c = 0) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } // 每个节点的价值 int v[N]; void dijkstra1() { memset(dist1, 0x3f, sizeof dist1); priority_queue<PII, vector<PII>, greater<PII>> q; dist1[1] = v[1]; q.push({dist1[1], 1}); while (q.size()) { int u = q.top().second; q.pop(); for (int i = h1[u]; ~i; i = ne[i]) { int j = e[i]; if (dist1[j] > min(dist1[u], v[j])) { dist1[j] = min(dist1[u], v[j]); q.push({dist1[j], j}); } } } } void dijkstra2() { memset(dist2, -0x3f, sizeof dist2); priority_queue<PII> q; dist2[n] = v[n]; q.push({dist2[n], n}); while (q.size()) { int u = q.top().second; q.pop(); for (int i = h2[u]; ~i; i = ne[i]) { int j = e[i]; if (dist2[j] < max(dist2[u], v[j])) { dist2[j] = max(dist2[u], v[j]); q.push({dist2[j], j}); } } } } int main() { // 正反两张图 // Q:为什么要反着建图，用正着的图不行吗？ // A:不行啊，因为从n向其它地方走，原来的有向图无法向对面走啊，反着建图就行了 memset(h1, -1, sizeof h1); memset(h2, -1, sizeof h2); scanf("%d %d", &n, &m); // n个节点，m条边 for (int i = 1; i <= n; i++) scanf("%d", &v[i]); // 每个节点购买水晶球的金额 while (m--) { int a, b, c; scanf("%d %d %d", &a, &b, &c); // 不管是单向边，还是双向边，第一条a->b的边肯定跑不了吧 if (c == 1) { // 单向边 // 正向图保存单向边 add(h1, a, b); // 反向图保存单向边 add(h2, b, a); // 注意：这可不是在一个图中创建两条来回的边，而是在两个图中创建两个相反的边。 // 权值呢？没有，为什么呢？因为我们不关心边权，而是关心此节点中水晶球的价格v[i]，这并不是边权,可以理解为点权 } else { // 双向边 // 正向图保存双向边 add(h1, a, b), add(h1, b, a); // 反向图保存双向边 add(h2, a, b), add(h2, b, a); } } // 正向图跑一遍dijkstra dijkstra1(); // 反向图跑一遍dijkstra dijkstra2(); int ans = 0; for (int i = 1; i <= n; i++) ans = max(dist2[i] - dist1[i], ans); printf("%d\n", ans); return 0; }dijkstra算法每个点只会扩展一次，图中代码每个点还是会松弛多次，以满足三角不等式。准确来说，应该叫扩展图中最短边的spfa算法
对滴。
两遍spfa
第一遍：从1走到i的最低价格
第二遍：从n走到i的最高价格
这样保证了可达性
所以建图的时候正反都建立了一遍
对于状态转移 d[j] = min(d[t], price[j])， 为什么不应该是 d[j] = min( d[t] , d[j] )，d[]数组初始化为price[] 呢？
我也想问这个问题，你现在弄明白了吗
因为前面有个条件：
flag && d[j] > min(d[t], price[j]) || !flag && d[j] < max(d[t], price[j]因为后效性，你当前传递的绝对数据是price,不能传递j, 这是因为存在环，可能你你收到j时，马上理解为dist[j]，可以，这时的dist[j]并不是你当时的数值。 举个栗子吧：
https://img-blog.csdnimg.cn/f553c1000eb04000a4fe36692462d41e.png
自己完全想不到啊！
有一点不是很理解，如果说最低的买入价格是3这个点，因为存在环，最高的卖出价格可能是1这个点，这样的话，岂不是以哪一个为中间点都求不出来差价的最大值
y总说这题不能用dp，可是spfa本质上不就是基于dp的吗？QAQ
if (flag) memset(d, 0x3f, sizeof dmin);
这步为什么将dmin改为d答案就不对了
d是指针，dmin是数组，输出sizeof d结果是8，输出sizeof dmin 结果是400040
感谢
用数组做函数参数时，可以将数组的长度也一并传进来，就OK了。不怕memset不对了，否则就返回 sizeof *h =8，就错了。
说实话我还是没搞懂为啥这题不能用dij，能详细解释一下嘛。。。。（/捂脸）
因为dij在本质上 只要出堆它的最小值就已经确定了，但是在这里y总说了，当点5出来的时候它的值是10，但是在后续更新中，会被点7更新成3。因为这里的更新方式是取min，跟一般的最短路问题还是有点区别的。
我感觉应该是这样的
这题我看y总的用spfa写过了。。。但是我自己改了下自己写的dij也过了。。。
你啥时候用dij过的 可以贴出来
我不知道咋在这里贴，你可以去看我打卡代码，我贴在上面啦
你应该是加了些优化把有些样例ac掉了，y总视频里说了加优化的确可以过，但是不推荐，出题人如果想卡你的话还是可以卡的
ok明白了~谢谢您~
不用谢
没错，很棒。
这题怎么感觉跟股票那题思路有点像，都是枚举分裂点
在这点上比较相似。
spfa O(nm) 这不tle了吗？
为什么这里dmin一开始不能全部初始化为w[i]呢？然后做spfa的时候不memset直接把第一个点放进去？然后更新的时候就是dist[j]=min(dist[j],dist[t]) 最大值同理。这样做为什么错啊
你这样跑第二遍spfa求最大值的时候，dist[j]的含义就不是价格了，而是最小，用最小更新最大，这个有问题吧
关于SPFA，它死了
为什么不强连通缩点后再dp呢
以每一个点作为分裂点，枚举它能到达n时所经过的左侧最小值与右侧最大值进行运算，最后得到结果
为了方便计算左侧最小值与右侧最大值，所以要采用双向建图的方式
求dmax[i]一定要倒着走吗
加指针有什么用啊， 代替数组吗
Dijkstra 可以用于有环图吗？
在dijikstra的模板题里就是存在环的，但是不能处理有负环的情况
只要带有负权边都不能处理，其余全都可以
哦哦是这么回事来着
Dij 不能做吗，为什么我 Dij 过了，是数据水吗？
我建图的时候分 3 层，第一层表示不买不卖，第二层表示买入，第三层表示卖出，发现就AC了。。。
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> Pii; int head[1500010],edge; struct Edge{ int v,w,nxt; }a[1500010]; inline void Add(int u,int v,int w){ a[++edge]=(Edge){v,w,head[u]}; head[u]=edge; } int n,m; priority_queue<Pii,vector<Pii>,greater<Pii> >q; int dis[300005]; // int vis[300005]; void Dijkstra() { memset(dis,0x3f,sizeof(dis)); dis[1]=0;q.emplace(0,1); while(!q.empty()) { auto[ww,now]=q.top();q.pop(); // if(vis[now]) continue; // vis[now]=1; for(int i=head[now];i;i=a[i].nxt) { int v=a[i].v,w=a[i].w; if(dis[v]>dis[now]+w) dis[v]=dis[now]+w,q.emplace(dis[v],v); } } } int W[100001]; signed main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) cin>>W[i]; for(int i=1,u,v,opt;i<=m;i++) { cin>>u>>v>>opt; for(int j=0;j<=2;j++) Add(u+j*n,v+j*n,0); Add(u,v+n,W[u]),Add(u+n,v+2*n,-W[u]); if(opt==2) { for(int j=0;j<=2;j++) Add(v+j*n,u+j*n,0); Add(v,u+n,W[v]),Add(v+n,u+2*n,-W[v]); } } Dijkstra(); cout<<max(0,-dis[3*n]); return 0; }严谨地说，你这个不是dij
你都把它保证时间复杂度的东西给注释掉了
这个是可以已经进队后还能进队的SPFA，所以本质上还是SPFA，而且时间复杂度还更劣了
其实dij应该是可以的吧？因为这个分层图里不会出现两个负边相连的情况。
这个就不是 Dijkstra 呀