Ceste
레이팅 미적용의견: 0
2.5 \(s / 128\) \(MB / 160\) points
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.
In test cases worth 40% of total points, it will hold 1 ≤ \(N\) , \(M\) , \(T\) {i}{ }, \(C\) {i}{ } ≤ 100.
The first line of input contains numbers \(N\) (1 ≤ \(N \le 2000\)), the number of cities, and \(M\) (1 ≤ \(M\)
≤ 2000), the number of roads.
Each of the following \(M\) lines contains four numbers, \(A\) {i}{ }, \(B\) {i}{ }, \(T\) {i}{ }, \(C\) {i}{ }, (1 ≤ \(A\) {i}{ }, \(B\) {i} ≤ \(N\) , 1 ≤ \(T\) { }, \(C\) ≤
2000) that denote there is a road connecting cities \(A\) {i} and \(B\) { }, that it takes \(T\) 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.
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.
4 4
1 2 2 4
3 4 4 1
4 2 1 1
1 3 3 1
8
3
14
4 5
1 2 1 7
3 1 3 2
2 4 5 2
2 3 1 1
2 4 7 1
7
6
44
3 2
1 2 2 5
2 1 3 3
9
-1
평가 및 의견
Ceste
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Ceste