题解

#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define MAXN 100005
using namespace std;

vector<int> adjList[MAXN];
int numNodes, numEdges, minCost[MAXN], maxCost[MAXN], cost[MAXN];

void dfs(int currentNode, int currentMin, int previousNode) {
    int flag = 1;
    currentMin = min(cost[currentNode], currentMin);
	if (minCost[currentNode] > currentMin) {
        minCost[currentNode] = currentMin;
        flag = 0;
    }
	int currentMax = max(maxCost[previousNode], cost[currentNode] - currentMin);
	if (maxCost[currentNode] < currentMax) {
        maxCost[currentNode] = currentMax;
        flag = 0;
    }
	if (flag) return;
	for (int i = 0; i < adjList[currentNode].size(); i++) {
        dfs(adjList[currentNode][i], currentMin, currentNode);
    }
}

int main() {
    cin >> numNodes >> numEdges;
    for (int i = 0; i < MAXN; i++) minCost[i] = INF;

    for (int i = 1; i <= numNodes; i++) cin >> cost[i];

    for (int i = 1; i <= numEdges; i++) {
        int node1, node2, edgeType;
        cin >> node1 >> node2 >> edgeType;
        adjList[node1].push_back(node2);

        if (edgeType == 2) adjList[node2].push_back(node1);
    }

    dfs(1, INF, 0);
    cout << maxCost[numNodes] << endl;

    return 0;
}