【题解】

这题就是要在n个点里面选一个花费最小的点。然后找一个花费最大的点。两者之差为最大值。

但是最大值的点要在最小值的点之后出现。且走到后者之后要能够到达N号节点。为了处理掉环。先用tarjan进行缩点。这样整张图就不会出现环了。接下来进行DP即可。记录到达某个点之前所能买到的最低价格。然后尝试在这个点卖掉。记录最优值。然后把最优值一直往后传。最后输出f[n]。这里的DP用了记忆化搜索。或者说是一个强力剪枝。自己看吧。

【代码】

//#pragma comment(linker,"/STACK:102400000,102400000")

#include <cstdio>

#include <vector>

#include <algorithm>

#include <stack>

using namespace std;

const int MAXN = 100000 + 100;

struct data2

{

    int sell, min;

};

int n, m, dx = 0, nn = 0, bh[MAXN];

int price[MAXN], dfn[MAXN], low[MAXN], ma_x[MAXN], mi_n[MAXN], ans = 0;

data2 f[MAXN];

vector <int> a[MAXN], aa[MAXN];

stack <int> z;

int zzz[MAXN];

bool flag[MAXN] = { 0 };

bool used[MAXN] = { 0 };

void tarjan(int x)

{

    flag[x] = true;

    dfn[x] = low[x] = ++dx;

    zzz[x] = z.size();

    z.push(x);

    int len = a[x].size();

    for (int i = 0; i <= len - 1; i++)

    {

        int y = a[x][i];

        if (!flag[y])

        {

            tarjan(y);

            low[x] = min(low[x], low[y]);

        }

        else

            if (zzz[y] >0)

                low[x] = min(low[x], dfn[y]);

    }

    if (low[x] == dfn[x])

    {

        nn++;

        int tma = price[x], tmi = price[x], limit = zzz[x];

        while (z.size() != limit)

        {

            int t = z.top();

            tma = max(tma, price[t]);

            tmi = min(tmi, price[t]);

            bh[t] = nn;

            zzz[t] = 0;

            z.pop();

        }

        ma_x[nn] = tma;

        mi_n[nn] = tmi;

    }

}

void dfs(int now, int pre)

{

    bool can = false; //这个can表示这个点有没有更新。如果没有更新任何东西就剪枝

    if (f[now].min > f[pre].min)

    {

        f[now].min = f[pre].min;

        can = true;

    }

    if (f[now].min > mi_n[now])

    {

        f[now].min = mi_n[now];

        can = true;

    }

    if (f[now].sell < ma_x[now] - f[pre].min)

    {

        f[now].sell = ma_x[now] - f[pre].min;

        can = true;

    }

    if (f[now].sell < ma_x[now] - mi_n[now])

    {

        f[now].sell = ma_x[now] - mi_n[now];

        can = true;

    }

    if (f[now].sell < f[pre].sell)//答案往后传

    {

        f[now].sell = f[pre].sell;

        can = true;

    }

    if (!can)

        return;

    int len = aa[now].size();

    for (int i = 0; i <= len - 1; i++)

        if (!used[aa[now][i]])

        {

            used[aa[now][i]] = true;

            dfs(aa[now][i], now);

            used[aa[now][i]] = false;

        }

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)

        scanf("%d", &price[i]);

    for (int i = 1; i <= m; i++)

    {

        int x, y, z;

        scanf("%d%d%d", &x, &y, &z);

        a[x].push_back(y);

        if (z == 2) a[y].push_back(x);

    }

    tarjan(1);

    for (int i = 1; i <= n; i++)

        if (bh[i] != 0)//bh数组记录了缩点后i号点新的编号

        {

            int len = a[i].size();

            for (int j = 0; j <= len - 1; j++)

            {

                int y = a[i][j];

                if (bh[y] != 0 && bh[i] != bh[y])

                    aa[bh[i]].push_back(bh[y]);

            }

        }

    for (int i = 1; i <= nn; i++)

        f[i].min = 2100000000;

    int qidian = bh[1];//从起点开始dfs+dp

    used[qidian] = true;

    f[qidian].min = mi_n[qidian];//一开始就可能在环里面

    f[qidian].sell = ma_x[qidian] - mi_n[qidian];

    int len = aa[qidian].size();

    for (int i = 0; i <= len - 1; i++)

        if (!used[aa[qidian][i]])

        {

            used[aa[qidian][i]] = true;

            dfs(aa[qidian][i], qidian);

            used[aa[qidian][i]] = false;

        }

    printf("%d\n", f[bh[n]].sell);

    return 0;

}