2679번 - 맨체스터의 도로 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 313 | 114 | 76 | 36.019% |
문제
맨체스터에 있는 도로는 모두 일방 통행이다. 또한 이 도로는 모두 1시간에 지나갈 수 있는 차의 개수 제한이 있다. 길(경로)에도 차의 개수 제한이 있는데, 이것은 이 길에 있는 도로의 제한 중 최솟값이다.
A에서 B로 가는 중복 비율은 A에서 B로 가는 모든 길을 동시에 이용했을 때 1시간 동안 B에 도착할 수 있는 차의 최대 개수와 길 1개를 이용했을 때 도착할 수 있는 최대 개수의 비율이다.
최소 중복 비율은 길 1개를 이용했을 때 도착할 수 있는 최대 개수가 가장 큰 값이 된다.
맨체스터의 도로 정보와 A, B가 주어졌을 때, 최소 중복 비율을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.
첫째 줄에 정수 4개가 주어진다. 차례대로 N, E, A, B이다. N (2 ≤ N ≤ 1,000)은 그래프의 정점의 개수, E (E ≥ 1)는 간선의 개수이다. A (0 ≤ A < N)와 B (0 ≤ B < N, A ≠ B)는 문제 설명에 나와있는 A와 B이다.
그 다음 E개 줄은 각 간선에 대한 정보이다. 이 정보는 U V W로 구성되어 있는데, U (0 ≤ U < N)와 V (0 ≤ V < N, V ≠ U)는 그래프의 정점이고, W (1 ≤ W ≤ 1000)는 U에서 V로 향하는 도로의 1시간에 지나갈 수 있는 차의 개수 제한이다.
출력
각 테스트 케이스에 대해 최소 중복 비율을 소수점 셋째자리까지 출력한다.
예제 입력 1
1 7 11 0 6 0 1 3 0 3 3 1 2 4 2 0 3 2 3 1 2 4 2 3 4 2 3 5 6 4 1 1 4 6 1 5 6 9
예제 출력 1
1.667
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호