代码的思路是分层图,分成三层写

其实这都不重要

第一层图和第二层图是负边权,第二层图和第三层是正边权,求最长路

每层图内部边权都是0

主要是函数用spfa过了,用dijkstra错了,我感觉差不多啊

求dalao看看代码中的dijstra和spfa有啥区别呜呜

#include <bits/stdc++.h>
using namespace std;
const int maxn=4e6+10;
int n,m,s,t,k;
int dis[maxn],vis[maxn],a[maxn];
struct edge{
	int to,w,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int w){
	d[cnt]=(edge){ v,w,head[u] },head[u]=cnt++;
}
typedef pair<int,int>p;
priority_queue<p,vector<p> >q;
void dijkstra(int s)
{
	for(int i=0;i<=3*n;i++)	dis[i]=-1e9;
	memset( vis,0,sizeof(vis) );
	dis[s]=0,q.push( p(0,s) );
	while( !q.empty() )
	{
		int now=q.top().second; q.pop();
		if( vis[now] )	continue;
		vis[now]=1;
		for(int i=head[now];i;i=d[i].nxt )
		{
			int v=d[i].to;
			if( dis[v]<dis[now]+d[i].w )
			{
				dis[v]=dis[now]+d[i].w;
				if( !vis[v] )	q.push( p(dis[v],v) );
			}
		}
	}
}
void spfa(int s)
{
	queue<int>q;
	for(int i=0;i<=3*n;i++)	dis[i]=-1e9;
	dis[s]=0,q.push(s);
	while( !q.empty() )
	{
		int now=q.front(); q.pop();
		vis[now]=0;
		for(int i=head[now];i;i=d[i].nxt)
		{
			int v=d[i].to;
			if( dis[v]<dis[now]+d[i].w )
			{
				dis[v]=dis[now]+d[i].w;
				if( !vis[v] )	vis[v]=1,q.push(v);
			}
		}
	}
}
int main()
{
	cin >> n >> m ;
	for(int i=1;i<=n;i++)	cin >> a[i];
	for(int i=1;i<=m;i++)
	{
		int l,r,ok;
		cin >> l >> r >> ok;
		add(l,r,0); add(l+n,r+n,0); add(l+2*n,r+2*n,0);
		add(l,r+n,-a[l]);
		add(l+n,r+2*n,a[l] );
		if( ok==2 )
		{
	    	add(r,l,0); add(r+n,l+n,0); add(r+2*n,l+2*n,0);
			add(r,l+n,-a[r] );
			add(r+n,l+2*n,a[r] );
		}
	}
	//dijkstra(1);
	spfa(1);
	cout << max(0,dis[3*n] );
}