记录编号	183359	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	1.364 s
提交时间	2015-08-31 10:26:55	内存使用	5.27 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
const int max_int=1061109567;
const int maxn=100010;
const int maxm=1010;

vector<int> G[maxn];
vector<int> rG[maxn];
int cost[maxn];
int d_min[maxn];
int d_max[maxn];
int n,m;

void spfa_min(int st)
{
    memset(d_min,0x3f,sizeof(d_min));
    queue<int> q;
    q.push(st);
    d_min[st]=cost[st];
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        int len=G[u].size();
        for(int i=0;i<len;i++)
        {
            int v=G[u][i];
            if(d_min[v]>d_min[u])
            {
                d_min[v]=d_min[u];
                q.push(v);
            }
            d_min[v]=min(d_min[v],cost[v]);
        }
    }
}

void spfa_max(int st)
{
    memset(d_max,-1,sizeof(d_max));
    queue<int> q;
    q.push(st);
    d_max[st]=cost[st];
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        int len=rG[u].size();
        for(int i=0;i<len;i++)
        {
            int v=rG[u][i];
            if(d_max[v]<d_max[u])
            {
                d_max[v]=d_max[u];
                q.push(v);
            }
            d_max[v]=max(d_max[v],cost[v]);
        }
    }
}


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",&cost[i]);
    }
	for(int i=1;i<=m;i++)
	{
        int a,b,c;scanf("%d%d%d",&a,&b,&c);
        G[a].push_back(b);
        rG[b].push_back(a);
        if(c==2)
        {
            G[b].push_back(a);
            rG[a].push_back(b);
        }
    }
    spfa_min(1);
    /*for(int i=1;i<=n;i++)
    {
        printf("%d ",d_min[i]);
    }
    printf("\n");*/
    spfa_max(n);
    int ans=-1;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,d_max[i]-d_min[i]);
    }
    printf("%d\n",ans);
	return 0;
}