题解：商人最大差价问题（图论 + 双向DP优化）

一、解题核心思路

本题的核心是找到从 1 号城市到 n 号城市的路径中，一次买卖的最大差价（买入价最低，卖出价最高，且买入在卖出之前）。由于城市和道路数量极大（n≤1e5，m≤5e5），暴力遍历所有路径不可行，需通过 双向动态规划 优化：

1. 正向DP（min_buy数组）：计算从 1 号城市出发，到达每个城市 u 时，所有路径中能找到的最低买入价（包括 u 本身及之前经过的所有城市）。
2. 反向DP（max_sell数组）：计算从每个城市 u 出发，到达 n 号城市时，所有路径中能找到的最高卖出价（包括 u 本身及之后经过的所有城市）。
3. 最大差价计算：遍历所有城市 u，max_sell[u] - min_buy[u] 的最大值即为答案（表示在 u 之前买入，u 之后卖出的最大收益）。

二、关键逻辑推导

• 为什么可行？
  商人的路径必然是 1→...→u→...→n，买入点在 1→u 的路径中，卖出点在 u→n 的路径中。因此：

  • min_buy[u] 是 1→u 路径中最低的买入价（无论如何到达 u）。
  • max_sell[u] 是 u→n 路径中最高的卖出价（无论如何从 u 到 n）。
  • 两者的差值就是以 u 为分界点的最大可能收益，遍历所有 u 即可得到全局最大值。

• 图的处理：

  • 正向图：用于计算 min_buy（从 1 出发的路径）。
  • 反向图：用于计算 max_sell（从 n 出发反向遍历，等价于正向路径 u→n）。
  • 双向道路 z=2 转化为两条单向道路（正向和反向各一条）。

三、具体解题步骤

步骤1：构建正向图和反向图

• 正向图 adj：存储每个城市的直接后继（道路通行方向）。
• 反向图 radj：存储每个城市的直接前驱（道路通行方向反转）。
• 双向道路 z=2 需在两个图中各添加两条反向边。

步骤2：计算 min_buy 数组（正向DP）

• 初始化：min_buy[1] = 1 号城市的价格，其余为无穷大（1e9）。
• 用队列实现 SPFA-like 遍历：从 1 号城市出发，遍历所有可达城市，更新 min_buy[v] = min(min_buy[u], 城市v的价格)（u 是 v 的前驱）。
• 核心：每次发现更低的买入价时，更新并重新入队，确保所有路径都被考虑。

步骤3：计算 max_sell 数组（反向DP）

• 初始化：max_sell[n] = n 号城市的价格，其余为0。
• 用队列实现 SPFA-like 遍历：从 n 号城市出发，遍历反向图的所有可达城市，更新 max_sell[u] = max(城市u的价格, max_sell[v])（v 是 u 在反向图中的前驱，即正向图中 u 的后继）。
• 核心：每次发现更高的卖出价时，更新并重新入队，确保所有路径都被考虑。

步骤4：计算最大差价

• 遍历所有城市 u，计算 max_sell[u] - min_buy[u]，取最大值。若最大值≤0，输出0（无收益）。

四、完整代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> price(n);
    for (int i = 0; i < n; ++i) {
        cin >> price[i];
    }

    // 构建正向图adj和反向图radj（1-based城市编号）
    vector<vector<int>> adj(n + 1), radj(n + 1);
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        // 正向边：x→y
        adj[x].push_back(y);
        radj[y].push_back(x);
        // 双向边额外添加y→x
        if (z == 2) {
            adj[y].push_back(x);
            radj[x].push_back(y);
        }
    }

    // 步骤1：计算min_buy[u]：1→u路径中最低价格（包括u）
    vector<int> min_buy(n + 1, INT_MAX);
    min_buy[1] = price[0];  // 城市1对应price[0]
    queue<int> q;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            // 到v的最低价格 = 到u的最低价格 和 v本身价格的最小值
            int current_min = min(min_buy[u], price[v - 1]);
            if (current_min < min_buy[v]) {
                min_buy[v] = current_min;
                q.push(v);
            }
        }
    }

    // 步骤2：计算max_sell[u]：u→n路径中最高价格（包括u）
    vector<int> max_sell(n + 1, 0);
    max_sell[n] = price[n - 1];  // 城市n对应price[n-1]
    q.push(n);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : radj[v]) {
            // u的最高卖出价 = u本身价格 和 v的最高卖出价的最大值
            int current_max = max(price[u - 1], max_sell[v]);
            if (current_max > max_sell[u]) {
                max_sell[u] = current_max;
                q.push(u);
            }
        }
    }

    // 步骤3：计算最大差价
    int ans = 0;
    for (int u = 1; u <= n; ++u) {
        ans = max(ans, max_sell[u] - min_buy[u]);
    }

    cout << ans << endl;

    return 0;
}

五、代码解释

1. 图的构建：

   • 正向图 adj 用于正向遍历（从 1 出发），反向图 radj 用于反向遍历（从 n 出发）。
   • 双向道路 z=2 转化为两条单向边，确保遍历覆盖所有可能路径。

2. 正向DP（min_buy）：

   • 初始时只有 1 号城市的价格已知，其他为无穷大。
   • 遍历每个城市的后继，更新后继的最低买入价（继承前驱的最低价格，或取自身价格）。
   • 队列确保所有可能的路径都被处理，即使存在环（价格范围仅 1~100，不会无限更新）。

3. 反向DP（max_sell）：

   • 初始时只有 n 号城市的价格已知，其他为0。
   • 遍历反向图的前驱（即正向图的后继），更新前驱的最高卖出价（继承后继的最高价格，或取自身价格）。

4. 最大差价计算：

   • 遍历所有城市，取 max_sell[u] - min_buy[u] 的最大值，确保收益非负（无收益时输出0）。

六、复杂度分析

• 时间复杂度：O(m)。由于价格范围仅 1~100，每个城市最多被更新 100 次（最低买入价最多降100次，最高卖出价最多升100次），总操作数约 5e7（m=5e5），完全适配数据规模。
• 空间复杂度：O(n+m)。存储两个邻接表和两个DP数组，空间开销可控。

该算法通过双向DP将复杂的路径遍历转化为高效的图遍历，完美解决了大规模图中的最大差价问题。