学步园

两遍spfa即可

SB地把L打成1。。。  居然还60分 。。。

code：

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<int> ljb[1000000];
vector<int>::iterator iv;
int n,m,x[1000000],y[1000000],v[1000000],maxn[1000000],minn[1000000],flag[1000000],
q[1000000],ans,i,l,r,p[1000000],pos;
bool relax(int x,int y){
	if (minn[x]<minn[y]){
		minn[y]=minn[x];
		return 1;
	}
	else return 0;
}
bool relax2(int x,int y){
	if (maxn[x]>maxn[y]){
		maxn[y]=maxn[x];
		return 1;
	}
	else return 0;
}
int main(){
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		scanf("%d",&v[i]);
	for (i=1;i<=m;i++)
		scanf("%d%d%d",&x[i],&y[i],&p[i]);
	//readln;
	for (i=1;i<=m;i++)
		if (p[i]==1)
		    ljb[x[i]].push_back(y[i]);
		else ljb[x[i]].push_back(y[i]),ljb[y[i]].push_back(x[i]);
	
	for (i=1;i<=n;i++)
	    minn[i]=100000000;
	minn[1]=v[1];
	l=0;r=1;q[r]=1;flag[1]=1;
	while (l!=r){
		l++;
		pos=q[l];
		flag[pos]=0;
		for (iv=ljb[pos].begin();iv!=ljb[pos].end();iv++){
			if (minn[*iv]>1000000){
				minn[*iv]=v[*iv];
				r++;
				q[r]=*iv;
				flag[*iv]=1;
			}
		    if (relax(pos,*iv))
		        if (!flag[*iv]){
					r++;
					q[r]=*iv;
					flag[*iv]=1;
				}
		}
	}
	//first spfa;
	for (i=1;i<=n;i++)
	    ljb[i].clear();
	memset(q,0,sizeof(q));
	for (i=1;i<=m;i++)
	    if (p[i]==1)
	        ljb[y[i]].push_back(x[i]);
	    else ljb[x[i]].push_back(y[i]),ljb[y[i]].push_back(x[i]);
	
	maxn[n]=v[n];
	l=0;r=1;q[r]=n;flag[n]=1;
	while (l!=r){
		l++;
		pos=q[l];
		for (iv=ljb[pos].begin();iv!=ljb[pos].end();iv++){
			if (maxn[*iv]==0){
				maxn[*iv]=v[*iv];
				r++;
				q[r]=*iv;
				flag[*iv]=1;
			}
		    if (relax2(pos,*iv))
		        if (!flag[*iv]){
					r++;
					q[r]=*iv;
					flag[*iv]=1;
				}
		}
	}
	//second spfa;
	for (i=1;i<=n;i++)
	    if (maxn[i]-minn[i]>ans)
	        ans=maxn[i]-minn[i];
	printf("%d",ans);
}