「NOIP2009」最优贸易

题意：在图上找一条从 $1$ 到 $n$ 的路径，是路径上选出两个点 $p,q$（满足 $p$ 在 $q$ 之前），使得节点 $q$ 的权值减去节点 $p$ 的权值最大。

在原图上用 $SPFA$ 或 $Dijkstra$ 求出数组 $D$，从 $1$ 出发，$D[x]$ 代表经过 $x$ 点时，已经过路径上最小的点权是多少；同理，建立一个反图，从 $n$ 出发，求出数组 $F$，$F[x]$ 代表经过 $x$ 点时，已经过路径上最大的点权是多少。数组的计算与单源最短路径的计算类似，如下：

$$D[y]=min(D[x],price[y]);F[y]=max(F[x],price[y])$$

最后直接枚举每个节点 $x$，求出最大的 $F[x]-D[x]$ 值。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int p[101010],d[101010],f[101010],vis1[101010],vis2[101010];
int head1[501010],cnt1,head2[501010],cnt2;
struct node
{
	int next;
	int to;
}e1[501010],e2[501010];
void add1(int from,int to)
{
	e1[++cnt1].next=head1[from];
	e1[cnt1].to=to;
	head1[from]=cnt1;
}
void add2(int from,int to)
{
	e2[++cnt2].next=head2[from];
	e2[cnt2].to=to;
	head2[from]=cnt2;
}
void spfa1()
{
	queue<int> q1;
	memset(d,0x3f,sizeof(d));
	d[1]=p[1];
	vis1[1]=1;
	q1.push(1);
	while(!q1.empty())
	{
		int u=q1.front();
		q1.pop();
		vis1[u]=0;
		for(int i=head1[u];i;i=e1[i].next)
		{
			int v=e1[i].to;
			if(d[v]>min(d[u],p[v]))
			{
				d[v]=min(d[u],p[v]);
				if(!vis1[v])
				{
					q1.push(v);
					vis1[v]=1;
				}
			}
		}
	}
}
void spfa2()
{
	queue<int> q2;
	memset(f,-1,sizeof(f));
	f[n]=p[n];
	vis2[n]=1;
	q2.push(n);
	while(!q2.empty())
	{
		int u=q2.front();
		q2.pop();
		vis2[u]=0;
		for(int i=head2[u];i;i=e2[i].next)
		{
			int v=e2[i].to;
			if(f[v]<max(f[u],p[v]))
			{
				f[v]=max(f[u],p[v]);
				if(!vis2[v])
				{
					q2.push(v);
					vis2[v]=1;
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(c==1)
		{
			add1(a,b);
			add2(b,a);
		}
		else
		{
			add1(a,b);
			add1(b,a);
			add2(a,b);
			add2(b,a);
		}
	}
	spfa1();
	spfa2();
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,f[i]-d[i]);
	printf("%d",ans);
	return 0;
}