CCO '21 P4 - Travelling Merchant

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type
Canadian Computing Olympiad: 2021 Day 2, Problem 1

A merchant would like to make a business of travelling between cities, moving goods from one city to another in exchange for a profit. There are N cities and M trading routes between them.

The i-th trading route lets the merchant travel from city a_i to city b_i (in only that direction). In order to take this route, the merchant must already have at least r_i units of money. After taking this route, the total amount of money the merchant has will increase by p_i units, with a guarantee that p_i \ge 0.

For each of the N cities, we would like to know the minimum amount of money required for a merchant to start in that city and be able to keep travelling forever.

Input Specification

The first line contains the two integers N and M (2 \le N, M \le 200\,000). The i-th of the next M lines contains the four integers a_i, b_i, r_i, and p_i (1 \le a_i, b_i \le N, a_i \ne b_i, 0 \le r_i, p_i \le 10^9). Note that there may be any number of routes between a pair of cities.

For 4 of the 25 available marks, N, M \le 2\,000.

For an additional 5 of the 25 available marks, p_i = 0 for all i.

Output Specification

On a single line, output N space-separated integers, where the i-th is the answer if the merchant were to start at city i. This answer is either the minimum amount of money, or -1 if no amount of money can be sufficient.

Sample Input

5 5
3 1 4 0
2 1 3 0
1 3 1 1
3 2 3 1
4 2 0 2

Sample Output

2 3 3 1 -1

Explanation for Sample Output

Starting from city 2 with 3 units of money, the merchant can cycle between cities 2, 1, and 3.


There are no comments at the moment.