COCI '17 Contest 4 #6 Ceste

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.2s
Memory limit: 128M

Problem type

There's a country with N cities and M bidirectional roads. Driving on road i takes T_i minutes, and costs C_i kunas (Croatian currency).

To make the arrival to the holiday destination as pleasant as possible, you want to make it as fast and as cheap as possible. More specifically, you are in city 1 and want to minimize the product of total money spent and total time spent (overall, with all roads you drove on) in getting to a city from city 1. For each city (except city 1), output the required minimal product or -1 if city 1 and that city aren't connected.

Input Specification

The first line of input contains numbers N (1 \le N \le 2\,000), the number of cities, and M (1 \le M \le 2\,000), the number of roads.
Each of the following M lines contains four numbers, A_i, B_i, T_i, C_i (1 \le A_i, B_i \le N, 1 \le T_i, C_i \le 2\,000) that denote there is a road connecting cities A_i and B_i, that it takes T_i minutes to drive on it, and it costs C_i kunas.
It is possible that multiple roads exist between two cities, but there will never be a road that connects a city with itself.

Output Specification

You must output N-1 lines. In the i^{th} line, output the required minimal product in order to get to city i+1, or -1 if cities 1 and i+1 aren't connected.

Scoring

In test cases worth 40\% of total points, it will hold 1 \le N, M, T_i, C_i \le 100.

Sample Input 1

4 4
1 2 2 4
3 4 4 1
4 2 1 1
1 3 3 1

Sample Output 1

8
3
14

Sample Input 2

4 5
1 2 1 7
3 1 3 2
2 4 5 2
2 3 1 1
2 4 7 1

Sample Output 2

7
6
44

Explanation for Sample Output 2

In order to get to city 2, you need to drive on road 1, for that it takes 1 minute and 7 kunas, so the required product is 7.
In order to get to city 3, you need to drive on road 2, for that it takes 3 minutes and 2 kunas, so the required product is 6.
In order to get to city 4, you need to drive on roads 2, 4, 5 in that order, and for that it takes a total of 11 minutes and 4 kunas, so the required product is 44.

Sample Input 3

3 2
1 2 2 5
2 1 3 3

Sample Output 3

9
-1

Comments


  • 1
    maxcruickshanks  commented on Nov. 2, 2022, 12:16 a.m.

    Since the original data were weak, an additional test case was added, and all submissions were rejudged.