시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 17 1 1 20.000%

문제

서울 내의 고속도로 도로망의 이용 요금이 빠르게 증가하고 있다. 때문에 최적의 경로를 찾는 것이 실제 문제로 제기되고 있다. 고속도로 도로망은 두 도시간의 양방향 도로들로 구성되어 있다. 각각의 도로에 대해 도로 이용요금과 도로를 지나가는데 걸리는 시간이 알려져 있다.

경로는 여행하는데 이용하는 도로들을 나열한 것을 의미한다. 경로상의 총 이용시간은 이동하는 도로들의 이용요금의 총합을 말한다. 또한 경로상의 총 요금은 경로상의 도로들을 지나가는데 걸리는 시간의 합을 의미한다. 그리고 경로상의 총 이용시간이 적을수록, 이용요금이 적을수록 더 좋은 경로가 된다. 즉, 어떤 경로가 다른 경로보다 좋다는 말은 이 경로가 다른 경로보다 빠르고 이용요금이 적다는 것을 의미한다. 우리는 어떠한 경로가 다른 어떤 경로보다도 좋은 경로일 때 이를 최적의 경로라 부른다. 하지만 항상 이러한 최적의 경로가 존재하는 것은 아니다.

예를 들어, 아래의 그림과 같은 고속도로 도로망이 있다고 하자. 각각의 도로는 요금과 이동하는데 걸리는 시간을 나타내는 한 쌍의 숫자로 구성되어진다,

그리고 도시 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)이 주어진다. 두 개 도시 사이에는 한 개 이상의 도로가 존재할 수 있다.

출력

첫 줄에 서로 다른 효율적인 비용-시간 쌍의 개수를 출력한다.

예제 입력

4 5 1 4
2 1 2 1
3 4 3 1
2 3 1 2
3 1 1 4
2 4 2 4

예제 출력

2

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2002 4번

  • 문제를 번역한 사람: author6
  • 문제의 오타를 찾은 사람: koosaga