Want to try solving this problem? You can submit your code online if you log in or register.

**Input File:** `trains.in`

**Output File:** `trains.out`

**Time Limit:** 1 second

**Memory Limit:** 32 MB

Melbourne's public transport system is in chaos. Due to a recent spate of brake failures, several of its new high-tech trains have been impounded and there are cancellations across the board. The train operators cannot fix the trains since this would take far too long, but the public are crying out for action. So the operators turn to a simpler solution that they are certain will make the public happy to be late — they offer discount vouchers.

Discount vouchers can be collected from a friendly customer service agent at any train station. Unfortunately the train operators are not renowned for communication, and so each train station is offering a different discount. For instance, you can pick up a measly $1-per-trip discount voucher from Flinders Street Station, whereas the lovely officials at Northcote will give you a $7-per-trip discount voucher if you smile sweetly.

A single voucher can be used for as many trips as you like. However, you
cannot combine multiple vouchers for a single trip (after all, the train
operators don't want you to deprive them of *all* their revenue).
You also cannot have a trip with negative cost (so, for instance, if you
use a $5 discount voucher on a $3 trip then the trip merely costs you
nothing, but you do not *earn* money).

As an example, suppose you are travelling through the network illustrated below. You begin your journey at Flinders Street, and your aim is to reach South Yarra.

The most direct route would seem to be via Collingwood and Clifton Hill. You begin at Flinders Street where they offer you a $1 discount voucher, and you travel to Collingwood with a cost of $5 - $1 = $4 for the trip. At Collingwood you pick up a $2 discount voucher, and use this to travel to Clifton Hill for free. You don't bother collecting a $1 voucher from Clifton Hill since you already have a $2 voucher which is better; instead you take the final leg to South Yarra with a cost of $10 - $2 = $8. The total cost of your trip is $4 + $8 = $12.

Suppose however that you decide to aim for that juicy $7 voucher at Northcote instead. You begin again at Flinders Street with your $1 discount voucher in hand, and this time travel direct to Northcote for $8 - $1 = $7. At Northcote you collect the $7 voucher and use it to travel to Clifton Hill for free. Using the $7 voucher again, the final leg from Clifton Hill to South Yarra costs $10 - $7 = $3, and the total cost of your journey is $7 + $3 = $10. With a little more investigation, it can be seen that $10 is the best that you can do.

Your task is to find a route between two given stations on the train system that costs you as little money as possible.

The first line of input will contain the single integer *n* representing the
number of train stations on the network
(1 <= *n* <= 200). These
stations are numbered 1,2,...,*n*.

The second line of input will contain the integers *s* and *f* separated by
a single space, where *s* is the station at which you start your journey
and *f* is the station at which you finish your journey
(1 <= *s*,*f* <= *n*).

The third line will contain *n* integers
*d*_{1} *d*_{2} ... *d _{n}*
separated by
single spaces, where these integers describe the various discount vouchers
that are available. In particular, each integer

The fourth line of input will contain the single integer *k*, where
*k* is
the number of different trips available on the train network. Following
this will be *k* additional lines of input, each describing a single
trip. Each of these lines will be of the form *x y c*, which means that
you can travel between station *x* and station *y* in either direction
at a cost of *c* dollars
(1 <= *x* < *y* <= *n* and
1 <= *c* <= 1,000,000).
Note that these costs are *before*
any discount vouchers are taken into account. No two trips in this list
will join the same pair of stations.

It is guaranteed that it will be possible to travel from station *s* to
station *f*.
Furthermore, for 70% of the available marks, it is guaranteed that
the number of stations will satisfy *n* <= 50.

Output should consist of a single integer, giving the lowest possible
cost of your journey from station *s* to station *f*. The dollar sign
must not be included in your output.

6 1 6 1 2 7 1 4 3 7 1 2 5 1 3 8 2 4 2 3 4 6 3 5 8 4 6 10 5 6 10

10

The sample input above represents the example scenario described earlier. Stations 1, 2, 3, 4, 5 and 6 are respectively Flinders Street, Collingwood, Northcote, Clifton Hill, Royal Park and South Yarra.

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 25 September 2022, 3:35am AEST