AcWing 341. 最优贸易 

题目：https://www.acwing.com/problem/content/343/

题目意思就是找到一条从1到n的路中的最大权值减去最小权值最大

建图，使用in[i]数组表示从1~i的路中的最小权值

建反向图，在反向图上用out[i]数组表示从n~i的路中的最大权值

最后遍历所有点，找出最大的out[i]-in[i]就是答案

题目：

#include<bits/stdc++.h>
using namespace std;
const int maxn1 = 1e5 + 7;
const int maxn2 = 1e6 + 7;
const int INF = 0x3f3f3f3f;
int in[maxn1], out[maxn1], num[maxn1];
int Head1[maxn1], To1[maxn2], Nxt1[maxn2]; //链式向前星建图
int Head2[maxn1], To2[maxn1], Nxt2[maxn2];
int tot1, tot2;
int n, m;
void add_edge(int fro, int to) { 
	Nxt1[++tot1] = Head1[fro]; //正向图
	To1[tot1] = to;
	Head1[fro] = tot1;
	Nxt2[++tot2] = Head2[to]; //反向图
	To2[tot2] = fro;
	Head2[to] = tot2;
}
typedef pair<int, int> P; //边，点
priority_queue<P, vector<P>, greater<P>>Q;
void Dijstra1() { //跑正向图
	memset(in, INF, sizeof(in));
	while (!Q.empty()) Q.pop();
	in[1] = num[1];
	Q.push(P(in[1], 1));
	while (!Q.empty()) {
		P p = Q.top(); Q.pop();
		int val = p.first, poi = p.second;
		if (in[poi] < val) continue;
		for (int i = Head1[poi]; i; i = Nxt1[i]) {
			int to = To1[i];
			if (in[to] > in[poi]) {
				in[to] = min(in[poi], num[to]);
				Q.push(P(in[to], to));
			}
		}
	}
}
void Dijstra2() { //跑反向图
	memset(out, 0, sizeof(out));
	out[n] = num[n];
	while (!Q.empty()) Q.pop();
	Q.push(P(out[n], n));
	while (!Q.empty()) {
		P p = Q.top(); Q.pop();
		if (out[p.second] > p.first) continue;
		for (int i = Head2[p.second]; i; i = Nxt2[i]) {
			int to = To2[i];
			if (out[to] < out[p.second]) {
				out[to] = max(num[to], out[p.second]);
				Q.push(P(out[to], to));
			}
		}
	}
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d",  num + i);
	}
	int fro, to, opt;
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &fro, &to, &opt);
		add_edge(fro, to);
		if (opt == 2) add_edge(to, fro);
	}
	Dijstra1();
	Dijstra2();
	int maxx = 0;
	for (int i = 1; i <= n; i++) {
		maxx = max(maxx, out[i] - in[i]);
	}
	printf("%d\n", maxx);
}

（更新中）