AcWing 341. 最优贸易 题解 （最短路、dp）

AcWing 341. 最优贸易
解题思路：先往dp方面想，将n个点视为n个状态的分界点，dp[k]表示以k为分界点，在k之前买进，在k之后卖出，n个状态会有重复的，但肯定不会有漏掉的（满足dp求最值的条件）。之后怎么求n个状态的dp值就成了关键，因为图可能会存在环，所以不能直接用状态转移dp，依然用spfa最短路径求，不过权值由边转移到了点上，但是道理相同。求两种最短路径，一种是能到达x点的最低的买入价，遍历由ht开头的邻接表记录正向边求得，另一种是求能到达x点的最大的卖出价，遍历由hs记录的逆向邻接表求得，求出每个点的两个值之后合计得出dp值，最后遍历找到最大的dp值就是答案

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 2e6 + 10;

int ht[N], hs[N], e[M], ne[M], w[M], idx;
int n, m;
bool st[N];
int dist[N];
int dmin[N], dmax[N];
int q[N];

void add(int h[], int a, int b){
    
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++ ;
}

void spfa(int h[], int dist[], int type){
    
	int hh = 0, tt = 1;
	if(type == 0){
    
		memset(dist, 0x3f, sizeof dmin);
		dist[1] = w[1];
		q[0] = 1;
	}
	else{
    
		memset(dist, -0x3f, sizeof dmax);
		dist[n] = w[n];
		q[0] = n;
	}
	
	while(hh != tt){
    
		int t = q[hh ++ ];
		if(hh == N) hh = 0;
		
		st[t] = false;
		
		for(int i = h[t]; ~i; i = ne[i]){
    
			int j = e[i];
			if((type == 0 && dist[j] > min(dist[t], w[j])) || (type == 1 && dist[j] < max(dist[t], w[j]))){
    
				if(type == 0) dist[j] = min(dist[t], w[j]);
				else dist[j] = max(dist[t], w[j]);
				
				if(!st[j]){
    
					q[tt ++ ] = j;
					if(tt == N) tt = 0;
					st[j] = true; 
				}
			}
		}
	}
} 

int main()
{
    
	cin>>n>>m;
	for(int i = 1; i <= n; i ++ ){
    
		scanf("%d", &w[i]);
	}
	
	memset(ht, -1, sizeof ht);
	memset(hs, -1, sizeof hs);
	
	while(m -- ){
    
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(ht, x, y);
		add(hs, y, x);
		if(z == 2){
    
			add(ht, y, x);
			add(hs, x, y);
		}
	}
	
	spfa(ht, dmin, 0);
	spfa(hs, dmax, 1);
	
	int res = 0;
	for(int i = 1; i <= n; i ++ ) res = max(res, dmax[i] - dmin[i]);  //求n个状态的dp值
	
	cout<<res<<endl;
	
	return 0;
}