1702번 - 고속도로 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 307 | 26 | 21 | 19.811% |
문제
서울 내의 고속도로 도로망의 이용 요금이 빠르게 증가하고 있다. 때문에 최적의 경로를 찾는 것이 실제 문제로 제기되고 있다. 고속도로 도로망은 두 도시간의 양방향 도로들로 구성되어 있다. 각각의 도로에 대해 도로 이용요금과 도로를 지나가는데 걸리는 시간이 알려져 있다.
경로는 여행하는데 이용하는 도로들을 나열한 것을 의미한다. 경로상의 총 이동시간은 경로상의 도로들을 지나가는데 걸리는 시간의 합을 의미한다. 또한 경로상의 총 요금은 이동하는 도로들의 이용요금의 총합을 말한다. 그리고 경로상의 총 이용시간이 적을수록, 이용요금이 적을수록 더 좋은 경로가 된다. 즉, 어떤 경로가 다른 경로보다 좋다는 말은 이 경로가 다른 경로보다 빠르고 이용요금이 적다는 것을 의미한다. 우리는 어떠한 경로가 다른 어떤 경로보다도 좋은 경로일 때 이를 최적의 경로라 부른다. 하지만 항상 이러한 최적의 경로가 존재하는 것은 아니다.
예를 들어, 아래의 그림과 같은 고속도로 도로망이 있다고 하자. 각각의 도로는 요금과 이동하는데 걸리는 시간을 나타내는 한 쌍의 숫자로 구성되어진다,
그리고 도시 1에서 도시 4로 가는데는 총 4가지 경로가 존재한다. 4가지 경로에 대해 총 이동시간과 요금을 계산하여 보면 1-2-4(요금 4, 시간 5), 1-3-4(요금 4, 시간 5), 1-2-3-4(요금 6, 시간 4), 1-3-2-4(요금 4, 비용 10)이 된다.
그리고 여기서 경로 1-3-4와 1-2-4가 경로 1-3-2-4보다 좋은 것을 알 수 있다. 이 도로망에서는 효율적인 요금-시간 쌍이 두 가지 존재한다. 요금 4, 시간 5(경로 1-2-4, 1-3-4), 요금 6, 시간 4(경로 1-2-3-4). 만약 요금을 많이 내더라도 빠른 길을 원한다면 경로 1-2-3-4를 선택하면 되고 반대로 시간은 조금 더 걸리더라도 요금을 적게 내고 싶으면 경로 1-3-4 또는 1-2-4를 선택하면 된다.
문제는 고속도로 도로망에 대한 정보가 주어지면 시작 도시에서 끝 도시까지 연결하는 효율적인 경로를 계산하는 것이다. 우리는 단지 서로 다른 효율적인 비용-시간 쌍의 개수만 출력하면 된다.
문제는 지역들이 노드로 구성된 그래프가 주어졌을 때 원샘이 원하는 지역 간의 거리를 신속히 알려주는 것이다.
입력
첫째 줄에 도시의 개수 n(1≤n≤100), 도로의 개수 m(1≤m≤300), 시작 도시 s, 도착 도시 e가 주어진다. (1≤s,e≤n, s≠e) 그 다음부터 m개의 줄에 도로에 대한 정보가 주어지는데 한 줄에 한 도로의 양 끝점 p, r(1≤p,r≤n, p≠r)과 요금 c(0≤c≤100), 그리고 시간 t(0≤t≤100)이 주어진다. 두 개 도시 사이에는 한 개 이상의 도로가 존재할 수 있다.
출력
첫 줄에 서로 다른 효율적인 비용-시간 쌍의 개수를 출력한다.
예제 입력 1
4 5 1 4 2 1 2 1 3 4 3 1 2 3 1 2 3 1 1 4 2 4 2 4
예제 출력 1
2
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호