#2146. Travelling Merchant
Travelling Merchant
Travelling Merchant
题目描述
2021 Canadian Computing Olympiad Day 2, Problem 1 Travelling Merchant Time Limit: 1 second Problem Description 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 ai to city bi (in only that direction). In order to take this route, the merchant must already have at least ri units of money. After taking this route, the total amount of money the merchant has will increase by pi units, with a guarantee that pi ≥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 ≤N, M ≤200 000). The i-th of the next M lines contains the four integers ai, bi, ri, and pi (1 ≤ai, bi ≤N, ai̸ = bi, 0 ≤ri, pi ≤109). Note that there may be any number of routes between a pair of cities. For 4 of the 25 available marks, N, M ≤2 000. For an additional 5 of the 25 available marks, pi = 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 Output for Sample Input 2 3 3 1 -1 Explanation of Output for Sample Input Starting from city 2 with 3 units of money, the merchant can cycle between cities 2, 1, and 3.
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 5
3 1 4 0
2 1 3 0
1 3 1 1
3 2 3 1
4 2 0 2
2 3 3 1 -1