AcWing 341. Optimal trade solution (shortest path, DP)

AcWing 341. The best trade
Their thinking ： The first dp Aspects , take n A point is regarded as n The dividing point of two states ,dp[k] Said to k It's the dividing point , stay k Bought before , stay k Sell later ,n There will be repetition in each state , But there must be nothing missing （ Satisfy dp The condition of finding the best value ）. How to ask after n A state of dp Value becomes the key , Because a graph may have rings , So you can't use state transfer directly dp, Still use spfa Find the shortest path , But the weight is transferred from edge to point , But the truth is the same . Find two shortest paths , One is to be able to reach x The lowest buying price of points , Traversal by ht The beginning adjacency table record is evaluated by the positive side , The other is seeking to reach x The maximum selling price of points , Traversal by hs The recorded inverse adjacency table is obtained , Calculate the two values of each point and then sum them up to dp value , Finally, traverse to find the largest dp The value is the answer

#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]);  // seek n A state of dp value 
	
	cout<<res<<endl;
	
	return 0;
}