写的不太好
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 2000010;
int hs[N], ht[N], e[M], ne[M], idx;
int w[N];
int dmin[N], dmax[N];
bool st[N];
int q[N];
int n, m;
void add(int h[], int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void spfa(int h[], int d[], int type) // d传入的是指针
{
int start = type? n : 1;
type? memset(d, 0xbf, sizeof dmax) : memset(d, 0x3f, sizeof dmin);
memset(st, 0, sizeof st);
int hh = 0, tt = 1;
q[0] = start;
d[start] = w[start];
st[start] = true;
while(tt != hh)
{
int t = q[hh ++];
if(hh == N) hh = 0;
st[t] = false;
for(int i = h[t]; ~i;i = ne[i])
{
int j = e[i];
if(!type && d[j] > min(d[t], w[j]) || type && d[j] < max(d[t], w[j]))
{
if(!type) d[j] = min(d[t], w[j]);
else d[j] = max(d[t], w[j]);
if(!st[j])
{
q[tt ++] = j;
if(tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i ++) scanf("%d", &w[i]);
memset(hs, -1, sizeof hs);
memset(ht, -1, sizeof ht);
while(m --)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(hs, a, b), add(ht, b, a);
if(c == 2) add(hs, b, a), add(ht, a, b);
}
spfa(hs, dmin, 0);
spfa(ht, dmax, 1);
int res = 0;
for(int i = 1;i <= n;i ++) res = max(res, dmax[i] - dmin[i]);
printf("%d\n", res);
return 0;
}