蒟蒻发错了，刚才那是存的旧代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
vector<int> g1[N], g2[N];
int dp[N][2];
int in[N];
int dfn[N];
int low[N];
int bl[N];
int dfs_clock, n, m, s, t, scc_cnt;
int val[N];
int mx[N];
int mn[N];
int sccno[N];
stack<int> st;
int min(int a, int b, int c)
{
return min(a, min(b, c));
}
void tarjan(int u)
{
dfn[u] = low[u] = ++dfs_clock;
st.push(u);
for(int i = 0; i < g1[u].size(); i++)
{
int v = g1[u][i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(!sccno[v])
{
low[u] = min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u])
{
scc_cnt++;
int x;
do
{
x = st.top();
st.pop();
bl[x] = u;
sccno[x] = scc_cnt;
mn[u] = min(mx[u],val[x]);
mx[u] = max(mx[u],val[x]);
} while(u != x);
}
}
void bfs()
{
queue<int> q;
for(int i = 1; i <= scc_cnt; i++)
{
if(!in[i])
{
q.push(i);
}
}
dp[s][0] = mn[s];
dp[s][1] = mx[s] - mn[s];
while(!q.empty())
{
int u=q.front();
q.pop();
in[u]=-1;
for(int i = 0; i < g2[u].size(); i++)
{
int v = g2[u][i];
dp[v][0] = min(dp[u][0], mn[v], dp[v][0]);
dp[v][1] = max(dp[v][1], mx[v] - dp[v][0]);
dp[v][1] = max(dp[v][1], dp[u][1]);
in[v]--;
if(!in[v])
{
q.push(v);
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
scanf("%d", &val[i]);
}
for(int i = 1; i <= m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
g1[x].push_back(y);
if(z == 2) g1[y].push_back(x);
}
for(int i = 1; i <= n; i++)
{
dp[i][0] = 1e9;
dp[i][1] = -1e9;
if(!dfn[i])
{
tarjan(i);
}
}
s = bl[1];
t = bl[n];
if(s == t)
{
printf("%d", mx[s] - mn[s]);
return 0;
}
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < g1[i].size(); j++)
{
int x = bl[i];
int y = bl[g1[i][j]];
if(x != y)
{
g2[x].push_back(y);
in[y]++;
}
}
}
bfs();
dp[t][1] = max(dp[t][1], 0);
printf("%d", dp[t][1]);
}
```
by WindyDay @ 2023-03-20 11:34:28