A17 正经题解

题意分析
求出一点到终点 $n$ 的所有路径上最大值和起点 $1$ 到该点的所有路径上最小值的差值的最大值。
解题思路
先从简单的链看：

1->2->3<->4<->5
价格:        4 1 6 3 2
到 n 最小值: 1 1 2 2 2
到 1 最大值: 4 4 6 6 6
差值:        3 3 4 4 4
最优:        4

看起来似乎和最短路关系不大，但实际上，这些最小值和最大值都需要最短路来维护。让 $SPFA$ 从点 $1$ 出发，在去点 $n$ 的过程中不断更新到每个点的最小值，切记不能搜到 $n$ 就停止，这样可能错过最优解。同理，从点 $n$ 出发再跑一遍，但维护的是到 $n$ 最大值。
$Dijkstra$ 无法判断先走哪条，$Bellman-Ford$ 时间复杂度 $O(n \times m)$ 必定超时，只能用 $SPFA$。有点像广搜，但 $SPFA$ 本就很像广搜。
AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
const int M = 5e5+5;
const int INF = 1e9+5;
vector<int> edge[N], reG[N];
int w[N], s[N], l[N];
bool in[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i=1;i<=n;++i){
        cin >> w[i];
        s[i] = INF;
    }
    for(int i=1;i<=m;++i){
        int u, v, op;
        cin >> u >> v >> op;
        edge[u].push_back(v);
        reG[v].push_back(u);
        if(op==2){
            edge[v].push_back(u);
            reG[u].push_back(v);
        }
    }
    queue<int> q;
    q.push(1);
    in[1] = true;
    s[1] = w[1];
    while(!q.empty()){
        int top = q.front();
        q.pop();
        in[top] = false;
        for(auto v:edge[top]){
            if(min(s[top], w[v])<s[v]){
                s[v] = min(s[top], w[v]);
                if(!in[v]){
                    q.push(v);
                    in[v] = true;
                }
            }
        }
    }
    q.push(n);
    in[n] = true;
    l[n] = w[n];
    while(!q.empty()){
        int top = q.front();
        q.pop();
        in[top] = false;
        for(auto v:reG[top]){
            if(max(l[top], w[v])>l[v]){
                l[v] = max(l[top], w[v]);
                if(!in[v]){
                    q.push(v);
                    in[v] = true;
                }
            }
        }
    }
    int ans = 0;
    for(int i=1;i<=n;++i){
        ans = max(ans, l[i]-s[i]);
    }
    cout << ans;
    
    return 0;
}

时间复杂度
$O(km)$，$k$是小常数，最坏情况 $O(nm)$，会超时，但本题没有这种毒瘤数据，而且可以写 $LLL$ 优化(虽然不能说效果好吧)。