记录编号	442717	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	liuyu	是否通过	通过
代码语言	C++	运行时间	0.242 s
提交时间	2017-08-28 11:58:11	内存使用	17.58 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z,a[100001],fi1[100001],ne1[1000001],w1[1000001],cnt1;
int fi2[100001],ne2[1000001],w2[1000001],cnt2,maxx[100001],minn[100001],ans;
bool b[100001];
queue<int> q;
void add1(int u,int v)
{
    w1[++cnt1]=v;ne1[cnt1]=fi1[u];fi1[u]=cnt1;
}
void add2(int u,int v)
{
    w2[++cnt2]=v;ne2[cnt2]=fi2[u];fi2[u]=cnt2;
}
void spfa(){
	q.push(1);b[1]=1;minn[1]=a[1];
    while(!q.empty())
    {
        int k=q.front();q.pop();b[k]=0;
        for(int i=fi1[k];i;i=ne1[i])
        {
            if(minn[w1[i]]>minn[k])
              {
                minn[w1[i]]=minn[k];
                if(!b[w1[i]])
                {
                    b[w1[i]]=1;q.push(w1[i]);
                }
              }
              if(minn[w1[i]]>a[w1[i]])
              {
                  minn[w1[i]]=a[w1[i]];
                  if(!b[w1[i]])
                {
                    b[w1[i]]=1;q.push(w1[i]);
                }
            }
        }
    }
    q.push(n);b[n]=1;maxx[n]=a[n];
    while(!q.empty())
    {
        int k=q.front();q.pop();b[k]=0;
        for(int i=fi2[k];i;i=ne2[i])
        {
            if(maxx[w2[i]]<maxx[k])
              {
                maxx[w2[i]]=maxx[k];
                if(!b[w2[i]])
                {
                    b[w2[i]]=1;q.push(w2[i]);
                }
              }
              if(maxx[w2[i]]<a[w2[i]])
              {
                  maxx[w2[i]]=a[w2[i]];
                  if(!b[w2[i]])
                {
                    b[w2[i]]=1;q.push(w2[i]);
                }
            }
        }
    }
}
int main()
{
	freopen("trade.in","r",stdin);
    freopen("trade.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);minn[i]=999999999;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add1(x,y);add2(y,x);
        if(z==2) add1(y,x),add2(x,y);
    }
    spfa();
    for(int i=1;i<=n;i++)
      if(maxx[i]-minn[i]>ans) ans=maxx[i]-minn[i];
    printf("%d\n",ans);
    return 0;
}