COCI 2013/2014 Contest 4- 달리기 > 문제은행 : 정보올림피아드&알고리즘




2021 : 달리기

제한시간
2000 ms   
메모리제한
128 MB   
해결횟수
2 회   
시도횟수
2 회   

문제

성재와 민혁이가 달리기 시합을 한다. 

먼저 시합의 주선자인 서연이가 N개의 지역 중 몇 곳의 지역을 골라서 

원형(출발 지점과 도착 지점이 같은) 트랙을 정한 후 둘이서 한 바퀴 돈다. 

서연이는 둘의 기록을 재고 승자를 결정한다. (당연히 완주시간이 짧은 쪽이 승자가 된다)


민혁이가 성재를 항상 이겨왔던 것을 지겨워하는 서연이는 성재가 완승하는 트랙을 만들고 싶어한다.


한편, 서연이는 성재와 민혁이의 달리기 기록을 알고 있는 길을 M개 알고 있다. 

민혁이가 이길 가능성을 아예 없애기 위해선 M개의 길들만으로 트랙을 만들어야 한다. 

한편, 경유 지역이 너무 많으면 주선자인 자신이 헷갈리기 때문에 경유 지역의 수는 최소화해야 한다.


서연이를 도와 성재가 완승하는 트랙을 구하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 지역의 수 N과 길의 수 M이 주어진다. (2 ≤ N ≤ 300, 2 ≤ M ≤ N(N-1)) 두 번째 줄부터 M개의 줄에는 길의 시작점과 끝점 Sk, Ek (1 ≤ Sk, Ek ≤ N, Sk ≠ Ek)와 성재와 민혁이의 기록(초)이 주어진다. 기록은 106 이하이다.

서브태스크 1 : N ≤ 11 서브태스크 2 : N ≤ 22 서브태스크 3 : N ≤ 111 서브태스크 4 : N ≤ 222 서브태스크 5 : 추가 제약 없음


출력형식

성재가 이기는 트랙 중 경유 지역의 수의 최솟값과, 그때 성재가 민혁이에 비해 앞설 수 있는 시간차의 최댓값을 출력한다. 단, 성재가 이기는 트랙은 항상 존재한다.


입력 예

3 4
1 2 3 0
2 3 3 0
3 1 0 100
2 1 0 4

출력 예

2 1

입력 예

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

출력 예

5 2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP