题解：强连通锁点之后。 就成了一副单向图。 然后对于每个点 找到 后面合法的点的最大值就好了。 合法就是后面的那个点可以走到n号点。

也可以正向跑一遍dij 求出到这个点的最小花费。 然后在反向跑dij跑出n到这个点的最大花费，然后枚举每个点。

代码：

#include
      
       using namespace std;#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);#define LL long long#define ULL unsigned LL#define fi first#define se second#define pb push_back#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define lch(x) tr[x].son[0]#define rch(x) tr[x].son[1]#define max3(a,b,c) max(a,max(b,c))#define min3(a,b,c) min(a,min(b,c))typedef pair
       
         pll;const int inf = 0x3f3f3f3f;const int _inf = 0xc0c0c0c0;const LL INF = 0x3f3f3f3f3f3f3f3f;const LL _INF = 0xc0c0c0c0c0c0c0c0;const LL mod =  (int)1e9+7;const int N = 1e5 + 100;const int M = 1e6 + 100;int head[N], to[M], nt[M], tot = 0;int a[N];vector
        
          vc[N];void add(int u, int v){    to[tot] = v;    nt[tot] = head[u];    head[u] = tot++;}int n, m, u, v, op;int belong[N], dfn[N], low[N], now_time, scc_cnt;int mx[N], mn[N], ret[N];stack
         
           s;void dfs(int u){    dfn[u] = low[u] = ++now_time;    s.push(u);    for(int i = head[u]; ~i; i = nt[i]){        if(!dfn[to[i]]) dfs(to[i]);        if(!belong[to[i]]) low[u] = min(low[u], low[to[i]]);    }    if(dfn[u] == low[u]){        ++scc_cnt;        int now;        while(1){            now = s.top(); s.pop();            belong[now] = scc_cnt;            if(now == u) break;        }    }}void scc(int n){    now_time = scc_cnt = 0;    for(int i = 1; i <= n; ++i)        if(!belong[i]) dfs(i);    int v;    for(int i = 1; i <= n; ++i){        for(int j = head[i]; ~j; j=nt[j]){            v = to[j];            if(belong[v] != belong[i]){                    vc[belong[i]].pb(belong[v]);            }        }    }    for(int i = 1; i <= n; ++i){        int rt = belong[i];        if(ret[rt] == 0){            ret[rt] = -1;            mn[rt] = a[i];            mx[rt] = a[i];        }        else {            mn[rt] = min(mn[rt], a[i]);            mx[rt] = max(mx[rt], a[i]);        }    }}int ans = 0;int solve(int x){    if(ret[x] != -1) return mx[x];    ret[x] = 0;    int mmax = -1;    if(x == belong[n]) mmax = mx[x];    for(int v : vc[x]){        mmax = max(solve(v), mmax);    }    if(mmax != -1) {        mx[x] = max(mx[x], mmax);        ans = max(ans, mx[x]-mn[x]);    }    else mx[x] = -1;    return mx[x];}int main(){    memset(head, -1, sizeof(head));    scanf("%d%d", &n, &m);    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);    for(int i = 1; i <= m; ++i){        scanf("%d%d%d", &u, &v, &op);        add(u, v);        if(op == 2) add(v, u);    }    scc(n);    solve(belong[1]);    cout << ans << endl;    return 0;}