NOIP2009提高组.最优贸易

题目

341. 最优贸易

算法标签: 最短路, $spfa$, 贪心

思路

处理从起点能够到达的所有点, 求到达该点的水晶球买入最小值, 然后从终点开始走反向边, 处理每个点能到达的卖出最大值, 然后枚举每个点, 计算能够获得的差价最大值是多少

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1000010, M = N * 4, INF = 0x3f3f3f3f;

int n, m;
int w[N];
int head[N], rhead[N], ed[M], ne[M], idx;
int min_val[N], max_val[N];
bool vis[N];
int q[N];

void add(int head[], int u, int v) {
   
	ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void spfa_min() {
   
	int h = 0, t = -1;
	q[++t] = 1;
	vis[1] = true;
	min_val[1] = w[1];

	while (h <= t) {
   
		int u = q[h++];
		vis[u] = false;

		for (int i = head[u]; ~i; i = ne[i]) {
   
			int v = ed[i];
			int val = min(min_val[u], w[v]);
			if (val < min_val[v]) {
   
				min_val[v] = val;
				if (!vis[v]) {
   
					q[++t] = v;
					vis[v] = true;
				}
			}
		}
	}
}

void spfa_max() {
   
	memset(vis, false, sizeof vis);
	int h = 0, t = -1;
	q[++t] = n;
	vis[n] = true;
	max_val[n] = w[n];

	while (h <= t) {
   
		int u = q[h++];
		vis[u] = false;

		for (int i = rhead[u]; ~i; i = ne[i]) {
   
			int v = ed[i];
			int val = max(max_val[u], w[v]);
			if (val > max_val[v]) {
   
				max_val[v] = val;
				if (!vis[v]) {
   
					q[++t] = v;
					vis[v] = true;
				}
			}
		}
	}
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);
	memset(rhead, -1, sizeof rhead);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> w[i];

	for (int i = 0; i < m; ++i) {
   
		int u, v, t;
		cin >> u >> v >> t;
		add(head, u, v);
		add(rhead, v, u);
		if (t == 2) {
   
			add(head, v, u);
			add(rhead, u, v);
		}
	}

	memset(min_val, 0x3f, sizeof min_val);
	spfa_min();
	spfa_max();

	int ans = 0;
	for (int i = 1; i <= n; ++i) {
   
		ans = max(ans, max_val[i] - min_val[i]);
	}

	cout << ans << "\n";
	return 0;
}