P1073 [NOIP 2009 Senior] Optimal Trade

本题原题数据极弱，Subtask 0 中的测试点为原题测试点，Subtask 1 中的测试点为 Hack 数据。

Country $C$ has $n$ major cities and $m$ roads, each connecting a pair of these $n$ cities. Between any two cities, there is at most one direct road. Among these $m$ roads, some are one-way and some are two-way. A two-way road is still counted as $1$ road. Because country $C$ is vast and resources vary by region, the price of the same commodity may differ between cities. However, the buy price and the sell price of the same commodity are always identical within the same city. A merchant, A-Long, is traveling in country $C$. After learning that the price of the same commodity may differ between cities, he decides to earn some travel money from price differences while touring. The cities in country $C$ are labeled from $1$ to $n$. A-Long will start from city $1$ and eventually end his trip in city $n$. During the trip, he may pass through any city multiple times, and he is not required to visit all $n$ cities. He will earn travel money in this way: he chooses a city he passes to buy his favorite commodity, a crystal ball, and later sells it in another city he passes, using the price difference as his travel funds. Since A-Long mainly came to travel, he will perform this trade at most once. If there is no profitable opportunity, he can choose not to trade. Suppose there are $5$ major cities in country $C$, with the city indices and road connections shown below. A single arrow indicates a one-way road, and a double arrow indicates a two-way road.  Assume the crystal ball prices in cities $1 \sim n$ are $4, 3, 5, 6, 1$. A-Long can choose the route $1 \to 2 \to 3 \to 5$, buy a crystal ball in city $2$ at price $3$, and sell it in city $3$ at price $5$, earning $2$. A-Long can also choose the route $1 \to 4 \to 5 \to 4 \to 5$, buy a crystal ball the first time he reaches city $5$ at price $1$, and sell it the second time he reaches city $4$ at price $6$, earning $5$. Given the crystal ball prices of $n$ cities and the information of $m$ roads (the indices of the two cities connected by each road and whether the road is one-way or two-way), please tell A-Long the maximum travel money he can earn.

The first line contains $2$ positive integers $n$ and $m$, separated by a space, representing the number of cities and the number of roads. The second line contains $n$ positive integers, separated by spaces, in index order, representing the commodity prices of the $n$ cities. The following $m$ lines each contain $3$ positive integers $x, y, z$, separated by spaces. If $z = 1$, the road is a one-way road from city $x$ to city $y$; if $z = 2$, the road is a two-way road between cities $x$ and $y$.

Output a single integer, the maximum travel money that can be earned. If no trade is performed, output $0$.

Constraints - It is guaranteed that city $1$ can reach city $n$. - For $10\%$ of the testdata, $1 \le n \le 6$. - For $30\%$ of the testdata, $1 \le n \le 100$. - For $50\%$ of the testdata, there is no tour route that starts from a city and returns to the same city. - For $100\%$ of the testdata: $1 \le n \le 100000$, $1 \le m \le 500000$, $1 \le x, y \le n$, $1 \le z \le 2$, and city prices $\le 100$. NOIP 2009 Senior, Problem 3. Translated by ChatGPT 5