详细题解

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

const int MAXN = 100005;

// 正向图和反向图
vector<int> forward_graph[MAXN];
vector<int> reverse_graph[MAXN];

int price[MAXN]; // 每个城市的价格
int min_price[MAXN]; // 从1到该城市的最低价格
int max_price[MAXN]; // 从该城市到n的最高价格
bool vis[MAXN]; // BFS访问标记

// 正向BFS：计算min_price
void forward_bfs(int start, int n) {
fill(min_price, min_price + n + 1, INT_MAX);
queue<int> q;
min_price[start] = price[start];
q.push(start);

while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = false;  // 取消标记，允许重复入队
    
    for (int v : forward_graph[u]) {
        // 更新v的最低价格
        if (min_price[v] > min(min_price[u], price[v])) {
            min_price[v] = min(min_price[u], price[v]);
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

}

// 反向BFS：计算max_price
void reverse_bfs(int end, int n) {
fill(max_price, max_price + n + 1, 0);
fill(vis, vis + n + 1, false);
queue<int> q;
max_price[end] = price[end];
q.push(end);
vis[end] = true;

while (!q.empty()) {
    int u = q.front();
    q.pop();
    
    for (int v : reverse_graph[u]) {
        // 更新v的最高价格
        if (max_price[v] < max(max_price[u], price[v])) {
            max_price[v] = max(max_price[u], price[v]);
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

}

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

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

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

// 建图
for (int i = 0; i < m; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    // 正向图：x->y
    forward_graph[x].push_back(y);
    reverse_graph[y].push_back(x);
    // 若为双向边，添加y->x
    if (z == 2) {
        forward_graph[y].push_back(x);
        reverse_graph[x].push_back(y);
    }
}

// 计算从1出发的最低价格
forward_bfs(1, n);
// 计算到n的最高价格（反向BFS从n出发）
reverse_bfs(n, n);

// 找最大差价
int ans = 0;
for (int i = 1; i <= n; ++i) {
    if (min_price[i] != INT_MAX && max_price[i] != 0) {
        ans = max(ans, max_price[i] - min_price[i]);
    }
}

cout << ans << endl;

return 0;

}

顺便打个广告：
https://www.acgo.cn/application/2003352214597373952