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 d1 d2 ... dn separated by single spaces, where these integers describe the various discount vouchers that are available. In particular, each integer di gives the dollar value of the discount voucher that can be collected from station i, where 0 <= di <= 1,000,000.
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
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.