P1073 [NOIP2009 提高组] 最优贸易

大佬题解

感觉分层图的做法太nb了吧，每次向下连边更新权值，我确实没什么补充的了，还是看大佬的吧。

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=1e7+10;
int n,m;
int val[N];

int cnt;
int head[N];
struct ss{
	int to,w,next;
}a[N];
void add(int u,int v,int w){
	a[cnt].to=v;
	a[cnt].w=w;
	a[cnt].next=head[u];
	head[u]=cnt++;
}

ll dis[N];
bool vis[N];

queue<int> q;

void spfa(){
	
	for(int i=1;i<=n*3;i++){
		dis[i]=INT_MIN;
	}
	dis[1]=0;
	q.push(1);
	vis[1]=1;
	
	while(!q.empty()){
		int u=q.front();
		q.pop();
		
		vis[u]=0;
		
		for(int i=head[u];~i;i=a[i].next){
			int v=a[i].to;
			if(dis[v]<dis[u]+a[i].w){
				dis[v]=dis[u]+a[i].w;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		} 
	}
	
}



int main(){
    ios::sync_with_stdio(false);
	memset(head,-1,sizeof head);
    cin>>n>>m;
    
    for(int i=1;i<=n;i++){
    	cin>>val[i];
	}
    
    for(int i=1;i<=m;i++){
    	int u,v,w;
    	cin>>u>>v>>w;
    	add(u,v,0);
		add(u+n,v+n,0);
		add(u+n+n,v+n+n,0);
		if(w==2){
			add(v,u,0);
			add(v+n,u+n,0);
			add(v+n+n,u+n+n,0);
		}	
	}
	
	for(int i=1;i<=n;i++){
		add(i,i+n,-val[i]);
		add(i+n,i+n+n,val[i]);
	}
	
	spfa();
	
	cout<<dis[n*3];
	
    return 0;
}