莫欺少年穷，修魔之旅在这开始—>算法提高课题解

DP + Spfa 的综合应用

时间复杂度： O(n+m)

思路：

1. DP思想：以 k 为分界点，从k前面买入最小值 dmin，从k后面卖出最大值 dmax，差价 = dmax - dmin
2. dmin：从 1 出发所有能到达 k 的点的最小值；dmax：从 n 出发所有能到达 k 的点的最大值
3. 这样就必定能保证可以从 1 走到 k，再从 k 走到 n，即 1 走到 n

#include<bits/stdc++.h>

using namespace std;

const int N = 100010, M = 2000010;

int n,m;
int w[N];
int hl[N],hr[N],e[M],ne[M],idx;
int dmin[N],dmax[N];
bool st[N];

void add(int h[],int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

//spfa求从起点到其它点的最短路或最长路
void spfa(int h[],int start,int dist[],int type)
{
    memset(st,0,sizeof st);

    if(!type) memset(dist,0x3f,sizeof dmin);
    dist[start]=w[start];

    queue<int> q;
    q.push(start);
    st[start]=true;

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        st[t]=false;

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(!type&&dist[j]>min(dist[t],w[j])||type&&dist[j]<max(dist[t],w[j]))
            {
                if(!type) dist[j]=min(dist[t],w[j]);
                else dist[j]=max(dist[t],w[j]);

                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>w[i];

    memset(hl,-1,sizeof hl);
    memset(hr,-1,sizeof hr);

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(hl,a,b),add(hr,b,a);
        if(c==2) add(hl,b,a),add(hr,a,b); 
    }

    //正向从1开始求一遍最短路
    spfa(hl,1,dmin,0);

    //反向从n开始求一遍最长路
    spfa(hr,n,dmax,1);

    //枚举分界点求最大值
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,dmax[i]-dmin[i]);

    cout<<res<<endl;

    return 0;
}