AcWing
341. 最优贸易
先求出：
- 从
1走到i的过程中，买入水晶球的最低价格dmin[i]； - 从
i走到n的过程中，卖出水晶球的最高价格dmax[i]；
然后枚举每个城市作为买卖的中间城市，求出dmax[i] - dmin[i]的最大值即可。
求dmin[i]和dmax[i]时，由于不是拓扑图，状态的更新可能存在环，因此不能使用动态规划，只能使用求最短路的方式。
最一般的最短路维护的是路径上的sum性质，本题维护的是max和min性质，sum性质具有累加性(就是要从前面的值基础上累加，后续出现只会越来越大，所以第一次出现的就是最短)，而max和min对于新出现的数，单独比较即可，所以不能用dijkstra(dijkstra就是利用的sum的累加性)。
例如，如果当前dmin[i]最小的点是5，那么有可能存在边 5->6，6->7，7->5，假设当前dmin[5] = 10，则有可能存在6的价格是11，但7的价格是3，那么dmin[5]的值就应该被更新成3，因此当前最小值也不一定是最终最小值，所以dijkstra算法并不适用，只能采用spfa算法。
需要正向、反向建两张图，以分别从1到i、从n到i(实际是从i到n)迭代spfa算法。
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 100010, M = 2000010;
int pmax[N], pmin[N];
int h[N], rh[N], e[M], w[N], ne[M], idx;
bool visited[N];
void add(bool wh, int a, int b){
if(!wh) e[idx] = b, ne[idx] = h[a], h[a] = idx++;
else e[idx] = b, ne[idx] = rh[a], rh[a] = idx++;
}
void spfa1(){
queue<int> q;
memset(visited, false, sizeof visited);
q.push(1);
pmin[1] = w[1];
visited[1] = 1;
while(!q.empty()){
int top = q.front();
visited[top] = 0;
q.pop();
for(int i = h[top]; ~i; i = ne[i]){
int j = e[i];
if(pmin[j] > min(pmin[top], w[j])){
pmin[j] = min(pmin[top], w[j]);
if(!visited[j]){
q.push(j);
visited[j] = 1;
}
}
}
}
}
void spfa2(){
queue<int> q;
memset(visited, false, sizeof visited);
q.push(n);
pmax[n] = w[n];
visited[n] = 1;
while(!q.empty()){
int top = q.front();
visited[top] = 0;
q.pop();
for(int i = rh[top]; ~i; i = ne[i]){
int j = e[i];
if(pmax[j] < max(pmax[top], w[j])){
pmax[j] = max(pmax[top], w[j]);
if(!visited[j]){
q.push(j);
visited[j] = 1;
}
}
}
}
}
int main(){
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
memset(pmax, -1, sizeof pmax);
memset(pmin, 0x3f, sizeof pmin);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> w[i];
while(m--){
int a, b, c;
cin >> a >> b >> c;
add(0, a, b);
add(1, b, a);
if(!(c - 2)){
add(0, b, a);
add(1, a, b);
}
}
spfa1();
spfa2();
int maxres = 0;
for(int i = 1; i <= n; i++){
if(pmax[i] - pmin[i] > maxres) maxres = pmax[i] - pmin[i];
// cout << pmax[i] << ' ' << pmin[i] << endl;
}
if(maxres) cout << maxres << endl;
else cout << 0 << endl;
return 0;
}