NOI '20 P1 - Delicacy

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

There are n cities numbered from 1 to n. The delicacy at city i may provide c_i units of happiness. The cities are connected by m one-directional roads, and the roads are numbered from 1 to m. Road i begins in city u_i and ends in city v_i. It takes w_i days to travel along road i. In other words, if one departs from city u_i and travels along road i on day d, then the person will arrive at city v_i on day d + w_i.

W is planning a trip lasting T days. More specifically, he will depart from city 1 on day 0, travel T days, and return to city 1 on day T exactly and finish the trip. Since W is an epicure, once W arrives in a city (including city 1 on day 0 and day T), he will try the delicacies in that city and gain some units of happiness. If W visits a city multiple times, he is able to gain the units of happiness multiple times. Notice that W may not stop at any city, which means if he arrives in a city and the trip hasn't ended, he must depart the city on the same day.

For the above example, a possible itinerary lasting 11 days for W is 1 \to 2 \to 1 \to 2 \to 3 \to 1. The total units of happiness of the trip is 13.

Moreover, there are k food festivals happening at different times. More formally, the i-th food festival is hosted in city x_i on day t_i. If W is in city x_i on t_i-th day, then he will obtain an additional y_i units of happiness for tasting the delicacies in city x_i. Now W wants to know the maximum possible units of happiness he may get from the trip.

Input Specification

The input begins with four integers n,m,T,K, denoting the number of cities, the number of roads, the length of the trip, and the number of food festivals. The second line contains n integers c_i denoting the units of happiness W may obtain from tasting the delicacies in each city. The following m lines contain three integers u_i,v_i,w_i each denoting the start, end, and the days required to travel along road i. The last k lines contain three integers t_i,x_i,y_i on each line, denoting the time of the food festival, the host city, and the additional units of happiness the food festival can provide.

The data guarantees: for all i, we have u_i \ne v_i. However, there might be parallel one-directional roads, or in other words, there may exist 1 \le i < j \le m such that u_i = u_j and v_i = v_j. For each city, there exists a road departing the city. The time of the food festivals t_i are distinct.

Output Specification

The output contains only one integer, denoting the maximum possible level of happiness W may obtain from the trip. If W cannot return to city 1 on day T, output -1.

Sample Input 1

3 4 11 0
1 3 4
1 2 1
2 1 3
2 3 2
3 1 4

Sample Output 1


Sample Input 2

4 8 16 3
3 1 2 4
1 2 1
1 3 1
1 3 2
3 4 3
2 3 2
3 2 1
4 2 1
4 1 5
3 3 5
1 2 5
5 4 20

Sample Output 2


The optimal itinerary is 1 \to 3 \to 4 \to 2 \to 3 \to 4 \to 1.


For all test cases, 1 \le n \le 50, n \le m \le 501, 0 \le k \le 200, 1 \le t_i \le T \le 10^9.
1 \le w_i \le 5, 1 \le c_i \le 52501, 1 \le u_i, v_i, x_i \le n, 1 \le y_i \le 10^9.

Test CasenmTAdditional Constraints
1~4\le 5\le 50\le 5None.
5~8\le 50\le 52501
9~10\le 10^9n = m and u_i = i, v_i = (i \bmod n) + 1.
11~13k = 0
14~15k \le 10
18~20\le 501


There are no comments at the moment.