프로그램 명: coci_utrka
제한시간: 2 초
민혁이와 진영이가 달리기 시합을 한다. 먼저 시합의 주선자인 성규가 N개의 지역 중 몇 곳의 지역을 골라서 원형(출발 지점과 도착 지점이 같은) 트랙을 정한 후 둘이서 한 바퀴 돈다. 성규는 둘의 기록을 재고 승자를 결정한다. (당연히 완주시간이 짧은 쪽이 승자가 된다)
성규는 진영이를 별로 안 좋아하기 때문에 진영이가 완패하기를 바란다. 따라서 성규는 민혁이가 이기는 트랙을 만들어야 한다.
한편, 성규는 민혁이와 진영이의 달리기 기록을 알고 있는 길을 M개 알고 있다. 진영이가 이길 가능성을 아예 없애기 위해선 M개의 길들만으로 트랙을 만들어야 한다. 또, 경유 지역이 너무 많으면 주선자인 자신이 헷갈리기 때문에 경유 지역의 수는 최소화해야 한다.
성규를 도와 진영이가 완패하는 트랙을 구하는 프로그램을 작성하여라.
입력 형식
- 첫 번째 줄에는 지역의 수 N과 길의 수 M이 주어진다. (2 ≤ N ≤ 300, 2 ≤ D ≤ N(N-1))
- 두 번째 줄부터 M개의 줄에는 길의 시작점과 끝점 Sk, Ek (1 ≤ Sk, Ek ≤ N, Sk ≠ Ek)와 민혁이와 진영이의 기록(초)이 주어진다. 기록은 10^6 이하이다.
출력 형식
민혁이가 이기는 트랙 중 경유 지역의 수의 최솟값과, 그때 민혁이가 진영이에 비해 앞설 수 있는 시간차의 최댓값을 출력한다. 단, 민혁이가 이기는 트랙은 항상 존재한다.
입력 예 1
3 4
1 2 3 0
2 3 3 0
3 1 0 100
2 1 0 4
출력 예 1
2 1
입력 예 2
5 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 0
출력 예 2
5 2
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 one-way roads, and for each road i we know Mi
and Si, 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.
INPUT
-
The first line of input contains two integers N, M (2 ≤ N ≤ 300, 2 ≤ M ≤ N(N-1)), the number of
villages and the number of connecting roads.
-
Each of the following M lines contains 4 integers Ai, Bi, Mi, Si (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi, 0 ≤ Si, Mi ≤
10^6). Respectively, the initial and ending village of the ith 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.
OUTPUT
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.
SAMPLE TESTS
input
3 4
1 2 3 0
2 3 3 0
3 1 0 100
2 1 0 4
output
2 1
input
5 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 0
output
5 2
출처:coci/2013-2014/contest4
번역:functionx
[질/답]
[제출 현황]
[푼 후(0)]