[NOIP 2009] 最优贸易

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010 
#define MAXM 500010

int i,n,m,x,y,z,tot,ans;
int a[MAXN],f[MAXN],g[MAXN],head[MAXN],rhead[MAXN];

struct edge
{
        int to,nxt;
} e[MAXM << 2];

inline void addedge(int u,int v)
{
        tot++;
        e[tot] = (edge){v,head[u]};
        head[u] = tot;
}
inline void addredge(int u,int v)
{
        tot++;
        e[tot] = (edge){v,rhead[u]};
        rhead[u] = tot;
}
/* Graph A, find minimum price  */
inline void spfa1() 
{
        int i,v,cur;
        queue< int > q;
        memset(f,0x3f,sizeof(f));
        f[1] = a[1];
        q.push(1);    
        while (!q.empty())
        {
                cur = q.front();
                q.pop();
                for (i = head[cur]; i; i = e[i].nxt)
                {
                        v = e[i].to;
                        if (min(f[cur],a[v]) < f[v])
                        {
                                f[v] = min(f[cur],a[v]);
                                q.push(v);
                        }
                }
        }
}
/* Graph B,find maximum price */
inline void spfa2() 
{
        int i,v,cur;
        queue< int > q;
        memset(g,0,sizeof(g));
        g[n] = a[n];
        q.push(n);
        while (!q.empty())
        {
                cur = q.front();
                q.pop();
                for (i = rhead[cur]; i; i = e[i].nxt)
                {
                        v = e[i].to;
                        if (max(g[cur],a[v]) > g[v])
                        {
                                g[v] = max(g[cur],a[v]);
                                q.push(v);
                        }
                }
        }
}

int main() 
{
        
        scanf("%d%d",&n,&m);
        for (i = 1; i <= n; i++) scanf("%d",&a[i]);
        for (i = 1; i <= m; i++)
        {
                scanf("%d%d%d",&x,&y,&z);
                if (z == 1)
                {
                        addedge(x,y);
                        addredge(y,x);
                } else
                {
                        addedge(x,y);
                        addedge(y,x);
                        addredge(x,y);
                        addredge(y,x);
                }
        }
        spfa1();
        spfa2();
        for (i = 1; i <= n; i++) ans = max(ans,g[i] - f[i]);
        printf("%d\n",ans);
        
        return 0;
    
}