#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; const int MAXN = 100005; // 存储每个城市的水晶球价格 int price[MAXN]; // 正向图和反向图的邻接表 vector<int> forwardGraph[MAXN], backwardGraph[MAXN]; // 从起点到每个城市的最小买入价格 int minBuy[MAXN]; // 从每个城市到终点的最大卖出价格 int maxSell[MAXN]; // 标记城市是否被访问过 bool visited[MAXN]; // 广度优先搜索，计算从起点到每个城市的最小买入价格 void bfsMinBuy(int start, int n) { queue<int> q; // 初始化最小买入价格为无穷大 fill(minBuy, minBuy + n + 1, INT_MAX); // 初始化访问标记数组 fill(visited, visited + n + 1, false); q.push(start); minBuy[start] = price[start]; visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : forwardGraph[u]) { if (!visited[v]) { // 更新最小买入价格 minBuy[v] = min(minBuy[v], minBuy[u]); minBuy[v] = min(minBuy[v], price[v]); q.push(v); visited[v] = true; } } } } // 广度优先搜索，计算从每个城市到终点的最大卖出价格 void bfsMaxSell(int end, int n) { queue<int> q; // 初始化最大卖出价格为负无穷大 fill(maxSell, maxSell + n + 1, INT_MIN); // 初始化访问标记数组 fill(visited, visited + n + 1, false); q.push(end); maxSell[end] = price[end]; visited[end] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : backwardGraph[u]) { if (!visited[v]) { // 更新最大卖出价格 maxSell[v] = max(maxSell[v], maxSell[u]); maxSell[v] = max(maxSell[v], price[v]); q.push(v); visited[v] = true; } } } } int main() { 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; if (z == 1) { forwardGraph[x].push_back(y); backwardGraph[y].push_back(x); } else { forwardGraph[x].push_back(y); forwardGraph[y].push_back(x); backwardGraph[x].push_back(y); backwardGraph[y].push_back(x); } } // 计算从起点到每个城市的最小买入价格 bfsMinBuy(1, n); // 计算从每个城市到终点的最大卖出价格 bfsMaxSell(n, n); int ans = 0; // 遍历每个城市，计算最大利润 for (int i = 1; i <= n; i++) { ans = max(ans, maxSell[i] - minBuy[i]); } cout << ans << endl; return 0; }