Earning Profit
本题没有可用的提交语言。
Description
You want to travel from city S to city T within your country. You have a list of available flights to choose from, and for each flight, you know the origin, destination, and the cost of the flight. However, these flights are not bidirectional, meaning that you can only use them to travel from one city to another, but not the other way around.
In each city you visit during your journey, you have the opportunity to close a deal and earn a profit. For each city i you visit, you can earn a profit of $P_i$ dollars and this deal can be done each time you visit a city. However, you must decide which cities to visit and which flights to take to maximize your profit.
Your objective is to reach city T with the maximum amount of money possible. To achieve this, you need to plan your journey carefully, taking into account the cost of flights and the potential profits in each city.
The first line contains four integers, $N$, $M$, $S$, and $T$ ($2 \leq N \leq 100, 1 \leq M \leq 10000, 1 \leq S, T \leq N$), where $N$ represents the number of cities in the country, $M$ represents the number of available flights, $S$ represents the city where your journey starts, and $T$ represents the city where you want to arrive.
The next $M$ lines each describe a flight with three integers: $U$, $V$, and $C$ ($1 \leq U, V \leq N$, $1 \leq C \leq 10^6$), where $U$ is the origin city of the flight, $V$ is the destination city, and $C$ is the cost of the flight.
The next line contains $N$ integers $P_1, P_2, \ldots, P_N$ ($0 \leq P_i \leq 10^6$), where $P_i$ represents the profit you can earn by closing a deal in city i.
An integer, the maximum profit you can earn when traveling from city S to city T. If it is impossible to reach city T from city S, output "Bad trip" and if you can earn infinite money with trading print "Money hack!".
Input
The first line contains four integers, $N$, $M$, $S$, and $T$ ($2 \leq N \leq 100, 1 \leq M \leq 10000, 1 \leq S, T \leq N$), where $N$ represents the number of cities in the country, $M$ represents the number of available flights, $S$ represents the city where your journey starts, and $T$ represents the city where you want to arrive.
The next $M$ lines each describe a flight with three integers: $U$, $V$, and $C$ ($1 \leq U, V \leq N$, $1 \leq C \leq 10^6$), where $U$ is the origin city of the flight, $V$ is the destination city, and $C$ is the cost of the flight.
The next line contains $N$ integers $P_1, P_2, \ldots, P_N$ ($0 \leq P_i \leq 10^6$), where $P_i$ represents the profit you can earn by closing a deal in city i.
Output
An integer, the maximum profit you can earn when traveling from city S to city T. If it is impossible to reach city T from city S, output "Bad trip" and if you can earn infinite money with trading print "Money hack!".
5 5 1 5
1 2 10
2 3 9
3 4 9
4 2 9
4 5 12
10 10 10 10 10
5 5 1 5
1 2 10
2 3 9
3 4 9
4 2 9
4 5 12
5 5 5 5 5
5 5 1 5
1 2 10
2 3 9
3 4 9
4 2 20
4 5 5
10 10 10 10 10
Money hack!
-20
7