Informatica Online Judge

  여행 가이드 [1086 / 043E]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 15   Total Tried : 29


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[UVAOJ]

Background

경곽이는 여행자 가이드 아르바이트를 했다.

요즘 경곽이가 하는 일은 단체관광객들을 원하는 도시로 데리고 가는 일을 한다.

경곽이가 안내하는 여행지는 N개의 도시와 M개의 왕복이 가능한 도로로 구성된다.

각 도시로 경곽이는 관광버스를 이용하여 이동하는데, 각 도로마다 탑승인원의 제한이 있다.

각 도시와 이들 도로간의 탑승인원의 제한 값을 알려주는 지도가 있다.

도로 사정에 따라서 관광객들을 한 번에 원하는 도시로 안내할 수 없는 경우도 있다.

이 때는 경곽이가 먼저 가능한 인원을 목적지로 데려다 주고 다시 관광버스를 몰고 출발 점으로 돌아와서 남은 인원을 테우고 이동해야하는 경우도 있다.

다음 예를 보자.





만약 출발지가 1이고 도착지가 5일, 관광객의 수가 10명일 때, 경곽이는 처음에 자신을 포함하여 11명(경곽이 + 관광객 10명)을 데리고 2번 도시로 갈 수 있다.

그러나 2번 도시에서 3번 도시로 가려면 탑승인원이 7명이므로 모두 갈 수 없다.

따라서 이 경로로 지나가기 위해서는 경곽이는 처음에 자신을 포함하여 7명만 태우고 갈 수 있다.

3번 도시에서 다시 5번 도시로는 10명이 탑승제한인원이므로 7명 모두 이동하면 관광객 경곽이를 제외한 6명이 일단 도착지에 도착한다.

이 경로를 이용하면 2회의 왕복으로 모든 관광객을 목적지로 데려갈 수 있다.

따라서 5번 도시로 최소 왕복 횟수는 2회이다.

광광지의 지도 정보 (도시의 수 N, 길의 수 M), 각 길의 제한인원, 그리고 출발지 S, 목적지 D, 관광객의 수 T가 주어질 때, 모든 관광객을 목적지로 데리고 가기 위한 목적지의 최소 방문 횟수를 구하는 프로그램을 작성하시오.

(단, 경곽이는 항상 광광버스에 탑승해야 한다. 즉, 경곽이가 버스를 운전하고, 경곽이도 제한인원에 포함된다.)

Input

첫 번째 줄에 도시의 수 N과 길의 수 M이 공백으로 구분되어 입력된다.
두 번째 줄에 출발 도시의 번호 S, 목적지의 번호 D, 관광객의 수 T가 공백으로 구분되어 입력된다.
세 번째 줄부터 M줄에 걸쳐서 도로를 연결하는 두 도시 a와 b, 그리고 두 도시간의 탑승제한인원 w가 공백으로 구분되어 입력된다.

[입력값의 정의역]
3 <= N <= 1,000
2 <= M <= 10,000
1 <= S, D <= M (단 S != D)
1 <= T <= 1,000,000,000
1 <= a, b <= N (단 a != b)
2 <= w <= 1,000,000,000

[Sub-Task Info]
#1 : N <= 10
#2 : N <= 100
#3 : 추가제한 조건은 없다.

Output

경곽이가 모든 관광객을 목적지에 데려가기 위하여 최소로 필요한 목적지 왕복 횟수를 출력한다.

IO Example

입력
5 5
1 5 10
1 2 20
2 3 7
2 4 8
3 5 10
4 5 7

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]