算法1

(双向spfa) $O(km)$

首先本题题意为：从节点1出发到一个价格最低的节点购买水晶球，再去一个价格最高的节点卖出水晶球，前提是买卖两个节点使可以到达的。因此可以考虑动态规划的思路，我们假设买卖由节点k分隔，即在节点1-k购买，在节点k-n卖出，当然也可以不买不卖，那么有：

• 从 1 走到 i 的过程中，买入水晶球的最低价格 dmin[i]；
• 从 i 走到 n的过程中，卖出水晶球的最高价格 dmax[i]；

那么显然最大差值为max(dmax[i] - dmin[i])，接下来考虑算法实现。求dmax[i] 和dmin[i]的过程显然使用最短路算法，由于这次求的最值是节点的权值最值，数值不累计，因此不能使用Dijkstra算法，于是采用spfa求最值，朴素的实现应该是先求节点1到各个节点最小值，然后分别求节点i到节点n的最大值，这样就等于执行了n次spfa，这样复杂度显然太高，于是考虑反向建图，即将图路径取反，然后求节点n到各个节点的最大距离，这样节点n到节点i的最大距离，就等于原图中节点i到节点n的最大距离，这样只需要执行两次spfa，节省了很多时间，可参考下边代码实现，代码参考yxc。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010, M = 2000010;

int n, m;
int price[N];
int h[N], rh[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 ++ ;
}

//寻找最小距离，flag来区分正反搜索
void spfa(int *d, int start, int *h, bool flag)
{
    queue<int> q;
    memset(st, 0, sizeof st);

    if (flag) memset(d, 0x3f, sizeof dmin);

    q.push(start);
    st[start] = true;
    d[start] = price[start];

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

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            //正搜求最小值，反搜求最大值
            if (flag && d[j] > min(d[t], price[j]) || !flag && d[j] < max(d[t], price[j]))
            {
                if (flag) d[j] = min(d[t], price[j]);
                else d[j] = max(d[t], price[j]);

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

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &price[i]);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        //add(rh, b, a)等是反向建图
        add(h, a, b), add(rh, b, a);
        if (c == 2) add(h, b, a), add(rh, a, b);
    }

    //分别进行一次spfa
    spfa(dmin, 1, h, true);
    spfa(dmax, n, rh, false);

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

    printf("%d\n", res);

    return 0;
}