这题好多种方法……Orz各路神仙
我先想到的是删与 1 和 n 点都连通的点，然后 Tarjan 缩点之后，枚举每个原图点作为买入点，然后维护和这个点连通的点(scc)权值最大值，减一下就行。
删点 DFS 标记一下，不过要建反图。和这个点连通的点(scc)权值最大值可以用 DP 求得，直接记忆化搜索一下。
然后第二种做法是做两次最短路松弛找到每个点$i$的$1,i$最小值，$i,n$最大值，之后枚举点更新即可。
第三种做法是 DFS。我们发现就只有三种情况，1、找一个点买，2、找一个点卖，3、到终点。
所以每次 DFS 三种情况，用数组可以判重。
第四种做法是 BFS。和DFS差不多。也可以 DP 思想跑 BFS。
第五种做法是 分层图最短路。这里 fy1234567ok 的思路，非常好，也就是把原图分层3个层，第一层是寻找买入点，第二层是寻找售出点，第三层是寻找n点。中间连边代表操作。对于没有贸易活动，直接连到超级n点处。
缩点+DP做法：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5, MAXM = 500000 + 5;
struct edge {int u, v, nxt; } ed[MAXM * 2], ed_2[MAXM * 2], ed_scc[MAXM * 2];
int n, m, c[MAXN], D[MAXN];
int en, en_2, en_scc, hd[MAXN], hd_2[MAXN], hd_scc[MAXN];
int lnkn[MAXN], lnk1[MAXN];
int low[MAXN], dfn[MAXN], vis[MAXN], sz, scc_sz, scc_belong[MAXN], scc_max[MAXN];
stack<int > s;
void ins(int u, int v) {ed[++en] = (edge){u, v, hd[u]}, hd[u] = en;}
void ins_2(int u, int v) {ed_2[++en_2] = (edge){u, v, hd_2[u]}, hd_2[u] = en_2;}
void ins_scc(int u, int v) {ed_scc[++en_scc] = (edge){u, v, hd_scc[u]}, hd_scc[u] = en_scc;}
void dfs1(int u) { // dfs on ed_2
for (int i = hd_2[u]; i > 0; i = ed_2[i].nxt) {
edge &e = ed_2[i];
if (!lnkn[e.v]) lnkn[e.v] = 1, dfs1(e.v);
}
}
void dfs2(int u) { // dfs on ed
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (!lnk1[e.v]) lnk1[e.v] = 1, dfs2(e.v);
}
}
void tarjan(int u) { // tarjan on ed
//if (!lnk1[u] || !lnkn[u]) return ;
low[u] = dfn[u] = ++sz, vis[u] = -1, s.push(u);
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (!vis[e.v]) {
//if (!lnk1[u] || !lnkn[u]) continue ;
tarjan(e.v);
low[u] = min(low[u], low[e.v]);
} else if (vis[e.v] == -1) low[u] = min(low[u], dfn[e.v]);
}
if (dfn[u] == low[u]) {
int e; ++scc_sz;
do {
e = s.top(); s.pop();
scc_belong[e] = scc_sz;
scc_max[scc_sz] = max(c[e], scc_max[scc_sz]);
vis[e] = 1;
} while (e != u);
}
}
int DP(int u) { ///dp on ed_scc
if (D[u] >= 0) return D[u];
int tmp = scc_max[u];
for (int i = hd_scc[u]; i > 0; i = ed_scc[i].nxt) {
edge &e = ed_scc[i];
tmp = max(tmp, DP(e.v));
}
return D[u] = tmp;
}
void clean() {
scc_sz = sz = en = en_2 = en_scc = 0, ms(hd, 0), ms(hd_2, 0), ms(hd_scc, 0);
ms(scc_max, 0), ms(D, -1), ms(vis, 0), ms(scc_belong, 0), ms(lnk1, 0), ms(lnkn, 0);
}
int solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);
clean();
for (int x, y, z, i = 1; i <= m; ++i) {
scanf("%d%d%d", &x, &y, &z);
if (z == 1) ins(x, y), ins_2(y, x);
else ins(x, y), ins(y, x), ins_2(x, y), ins_2(y, x);
}
lnkn[n] = 1, dfs1(n);
lnk1[1] = 1, dfs2(1);
if(!lnkn[1]) return printf("0\n"), 0;
// for (int i = 1; i <= n; ++i) printf("%d ", lnk1[i]);
// putchar('\n');
// for (int i = 1; i <= n; ++i) printf("%d ", lnkn[i]);
for (int u = 1; u <= n; ++u) if (!lnk1[u] || !lnkn[u]) vis[u] = 1;
tarjan(1);
// for (int i = 1; i <= n; ++i) printf("%d ", scc_belong[i]);
for (int u = 1; u <= n; ++u) {
if (!lnk1[u] || !lnkn[u]) continue ;
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (scc_belong[u] != scc_belong[e.v]) ins_scc(scc_belong[u], scc_belong[e.v]);
}
}
DP(scc_belong[1]);
// for (int i = 1; i <= scc_sz; ++i) printf("%d ", D[i]);
int ans = 0;
for (int st = 1; st <= n; ++st) ans = max(ans, D[scc_belong[st]] - c[st]);
printf("%d\n", ans);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
