解法 1（Tarjan + 拓扑排序 + 动态规划）

先用 Tarjan 算法进行强连通分量缩点，接着考虑给定图是一个 DAG 的时候怎么做。记 $w_{1\ u}$ 表示编号为 $u$ 的强连通分量中的最小权值，而 $w_{2\ u}$ 表示编号为 $u$ 的强连通分量中的最大权值。

考虑动态规划，设计两个状态：$f_u$ 表示从 $1$ 到 $u$ 的路径上的最小花费，初始值为 $w_{1\ u}$；$g_u$ 表示从 $1$ 开始，到 $u$ 为止，最大收入的贸易方式，初始值为 $w_{2\ u}-w_{1\ u}$。

那么进行边 $u\to v$ 的状态转移时，应该先用 $f_u$ 更新 $f_v$ 的值，再更新 $g_v$ 的值。而 $g_v$ 则可以用 $\min\{g_u,\ w_{2\ v}-f_u\}$ 来更新。

故只需先拓扑排序再进行状态转移即可。

解法 2（搜索 + 哈希判重，乱搞）

记一个状态三个值：现在所在点 $id$，现在所处阶段 $t$，答案 $ans$。其中 $t=1$ 表示还未买入；$t=2$ 表示已经买入但是没有卖出；$t=3$ 表示已经卖出。

那么直接搜索哈希判重即可。

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define MAXN 100005
using namespace std;

vector<int> g[MAXN];
int n,m,f[MAXN],mi[MAXN],c[MAXN];

void dfs(int x,int minx,int pre) {
    int flag=1; 
    minx=min(c[x],minx);
    if (mi[x]>minx) mi[x]=minx,flag=0;
    int maxx=max(f[pre],c[x]-minx);
    if (f[x]<maxx) f[x]=maxx,flag=0;
    if (flag) return;
    for (int i=0;i<g[x].size();i++) dfs(g[x][i],minx,x);
}

int main() {
    scanf("%d%d",&n,&m);
    for (int i=0;i<MAXN;i++) mi[i]=INF;
    for (int i=1;i<=n;i++) scanf("%d",&c[i]);
    for (int i=1;i<=m;i++) {
        int t1,t2,t3;
        scanf("%d%d%d",&t1,&t2,&t3);
        g[t1].push_back(t2);
        if (t3==2) g[t2].push_back(t1);
    }
    dfs(1,INF,0);
    printf("%d\n",f[n]);
    return 0;
}

539