Felix Halim .NET |  |

| Enter your search terms Submit search form

Story | Research | Programming | Scripts | Member | Miscellaneous

### ACM/ICPC Indonesia National Contest 2007 - Qualification

## Problem E

# Taxi!

Time Limit: 1s

Taxi Driver | : "Where to go, sir?"
Passenger | : "Kemanggisan, Binus Campus, please."
Taxi Driver | : "Okay, and which way to go?"
Passenger | : "Just take the fastest one."

This kind of conversation usually happens when we take a taxi. Many people think that the fastest way would mean the cheapest one as well. But it�s not always true! Sometimes the fastest way could be more expensive than the slower one and vice versa, some factors are: toll fee, longer road without traffic jam, etc.
We will model this kind of situation on this problem. The city has n intersections and m bidirectional roads connecting pairs of intersections. Each road will cost you a certain time and money (taxi fare). Write a program to find the minimum time to take you to your destination however the travel expenses must not exceed your money.

## Input Specification

The first line of each case contains two integers, n (1 <= n <= 100) intersections and m roads. The intersections are numbered from 0 to n-1. The next m lines will each contains four integers: u, v, t, and c (1 <= t,c <= 100), means that there is a road from intersection u to intersection v and vice versa which will cost you t minute(s) and c Rupiah(s). The last line of each case will contains three integers: s, d, and r (1 <= r <= 100), means that you want to go to d (your destination point) from s (your starting point) while you only have r Rupiah(s).

## Output Specification

For each case, output in a single line the minimum time to reach your destination while the total cost doesn�t exceed your money.

## Sample Input

    3 3
    0 2 16 19
    0 1 9 12
    1 2 5 13
    0 2 20
    4 5
    0 1 2 11
    1 2 7 27
    2 3 4 10
    0 3 6 25
    3 1 5 12
    0 2 35

## Sample Output

    16
    10

Problem Setter: Suhendry Effendy

Kembali ke pembahasan soal ini

Lihat problem lain:

1. The Chosen Sub Matrix
2. Avoiding Financial Nightmare
3. No Pause Telegraph
4. Burger, French Fries, Soft Drink
5. Taxi!

`© Felix Halim 2009 (Loaded in 0.01741 secs)`

    Timeline:
    start_time (diff_time_with_previous) tree_structure
    0.00000 (0.00000) Total
    0.00002 (0.00002) -Logging Request
    0.00005 (0.00003) --Creating fhnet PDO...
    0.01530 (0.01524) --fhnet PDO created
    0.01534 (0.00004) --Statement created
    0.01680 (0.00146) --Statement executed

    Summary:
    start_time (duration) section_name
    0.00000 (0.01743) : Total
    0.00002 (0.01680) : Logging Request