Utrka
레이팅 미적용의견: 0
\(4^{th}\) round, January \(18^{th}\), 2014
Mirko and Slavko are the only two contestants at the Grand Prix of Dabrovina Donja which is driven
through nearby villages. The villages are connected via o\(ne-wa\)y roads, and for each road i we know M_{i}
and S_{i}, the time necessary for Mirko and Slavko to cross that road. The race itself is circular (meaning it
starts and begins in the same village), but the route itself hasn't been determined yet.
Mirko has bribed the organisers of the race so they'd pick a route in his favour. Specifically, the
organisers are going to pick the shortest route (containing the minimal number of roads) such that
Mirko is strictly faster than Slavko on that route. If, by any chance, there are several such routes, the
organisers choose the one where Mirko gains maximal advantage.
The first line of input contains two integers N, M (\(2 \le N \le 300\), \(2 \le M \le N\)(\(N-1\))), the number of
villages and the number of connecting roads.
Each of the following M lines contains 4 integers A_{i}, B_{i}, M_{i}, S_{i} (\(1 \le A_{i}\), \(B_{i} \le N\), \(A_{i} \ne B_{i}\), \(0 \le S_{i}\), M_{i} ≤
\(10^{6}\)). Respectively, the initial and ending village of the i^{th} road, the time necessary for Mirko and the
time necessary for Slavko to cross that road. There won't exist two different roads that connect the
same pair of villages in the same direction.
The first and only line of output must contain two integers: the shortest possible route (with the
minimal number of roads) such that Mirko wins, and the maximal advantage Mirko can gain on a route
of the shortest length.
Please note: The input data will be such that a route which meets the conditions from the text will
always exist.
3 4
1 2 3 0
2 3 3 0
3 1 0 100
2 1 0 42 15 7
1 2 4 1
2 3 5 1
3 1 1 6
1 3 15 5
2 4 7 5
4 5 1 4
5 3 1 05 2평가 및 의견
Utrka
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Utrka