nyoj 247

题意：从1-n的一条路径中，找出两点，使得两点权值之差最大。n个点不一定要都经过。

解题思路：这道题实际可以转化为找出可达的两点a，b，使得a和b两点的权值之差最大。。。这道题确实很难想到是转化为最短路的模型，我开始还是按照论坛里面说的，先求强连通分量、缩点，最后再搜索，结果挂了。。

假设最后的结果是a-b，那么我们肯定要保证a>b，否则根据题意就无意义。并且我们还应该要有b->a，即可以从b走到a，那么就定义两个数组d_min[i]，和d_max[i]，分别表示从1->i经过点的最小值和从i->n经过点的最大值，最后只需找到最大的d_max[i] - d_min[i]即可。为了方便求d_max[i]，我们应该要从n出发寻找，所以应该要建立反向边。

注意：这里是能够保证我们之前讲的两条性质，注意到d_min和d_max表示的意义，是1->i和i->n所经过的点的最小和最大值，如果a在b的前面，那么肯定d_max和d_min不会同时包含a和b的（画图即可明白），如果a<b，毫无疑问肯定算出的不会是最优值。

这里算d_min和d_max可以用spfa算法，确实spfa算法在最短路里面的应用非常广。总之这样运用spfa还是第一次见。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int maxn = 100005;
struct Edge
{
	int k,next;
}edge[maxn<<2];
int n,m,cnt,d_max[maxn],d_min[maxn];
int head1[maxn],head2[maxn];
bool s1[maxn],s2[maxn];

void addedge(int u,int v)
{
	edge[cnt].k = v;
	edge[cnt].next = head1[u];
	head1[u] = cnt++;

	edge[cnt].k = u;
	edge[cnt].next = head2[v];
	head2[v] = cnt++;
}

void spfa()
{
	queue<int> q;
	memset(s1,false,sizeof(s1));
	memset(s2,false,sizeof(s2));
	q.push(1);
	s1[1] = true;
	while(!q.empty())
	{
		int t = q.front();
		q.pop();
		for(int i = head1[t]; i != -1; i = edge[i].next)
		{
			int k = edge[i].k;
			d_min[k] = min(d_min[t],d_min[k]);
			if(s1[k] == false)
			{
				s1[k] = true;
				q.push(k);
			}
		}
	}
	q.push(n);
	s2[n] = true;
	while(!q.empty())
	{
		int t = q.front();
		q.pop();
		for(int i = head2[t]; i != -1; i = edge[i].next)
		{
			int k = edge[i].k;
			d_max[k] = max(d_max[t],d_max[k]);
			if(s2[k] == false)
			{
				s2[k] = true;
				q.push(k);
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
		if(s1[i] && s2[i])
		{
			ans = max(ans,d_max[i] - d_min[i]);
		}
	printf("%d\n",ans);
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(head1,-1,sizeof(head1));
		memset(head2,-1,sizeof(head2));
		cnt = 0;
		for(int i = 1; i <= n; i++)
		{
			scanf("%d",&d_max[i]);
			d_min[i] = d_max[i];
		}
		for(int i = 1; i <= m; i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			addedge(x,y);
			if(z == 2)
				addedge(y,x);
		}
		spfa();
	}
	return 0;
}