#include <iostream> #include <vector> #include <queue> #include <climits> #include <algorithm> using namespace std; const int MAXN = 100005; // 存储图的邻接表 vector<int> forwardGraph[MAXN]; vector<int> backwardGraph[MAXN]; // 存储每个城市水晶球的价格 int prices[MAXN]; // 存储从 1 号城市到各城市的最小价格 int minPrices[MAXN]; // 存储从 n 号城市到各城市的最大价格 int maxPrices[MAXN]; // 标记节点是否被访问过 bool visited[MAXN]; // 正向 BFS，计算从 1 号城市到各城市的最小价格 void bfsMinPrice(int n) { fill(minPrices, minPrices + n + 1, INT_MAX); fill(visited, visited + n + 1, false); queue<int> q; q.push(1); visited[1] = true; minPrices[1] = prices[1]; while (!q.empty()) { int city = q.front(); q.pop(); for (int neighbor : forwardGraph[city]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } minPrices[neighbor] = min(minPrices[neighbor], min(minPrices[city], prices[neighbor])); } } } // 反向 BFS，计算从 n 号城市到各城市的最大价格 void bfsMaxPrice(int n) { fill(maxPrices, maxPrices + n + 1, 0); fill(visited, visited + n + 1, false); queue<int> q; q.push(n); visited[n] = true; maxPrices[n] = prices[n]; while (!q.empty()) { int city = q.front(); q.pop(); for (int neighbor : backwardGraph[city]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } maxPrices[neighbor] = max(maxPrices[neighbor], max(maxPrices[city], prices[neighbor])); } } } // 计算最大利润 int maxProfit(int n) { int profit = 0; for (int i = 1; i <= n; ++i) { profit = max(profit, maxPrices[i] - minPrices[i]); } return profit; } int main() { int n, m; cin >> n >> m; // 读取每个城市的水晶球价格 for (int i = 1; i <= n; ++i) { cin >> prices[i]; } // 读取道路信息并构建正向和反向图 for (int i = 0; i < m; ++i) { int x, y, z; cin >> x >> y >> z; forwardGraph[x].push_back(y); backwardGraph[y].push_back(x); if (z == 2) { forwardGraph[y].push_back(x); backwardGraph[x].push_back(y); } } // 进行正向和反向 BFS bfsMinPrice(n); bfsMaxPrice(n); // 计算并输出最大利润 cout << maxProfit(n) << endl; return 0; }