ZOJ Problem Set - 2963
As an RPG (Role Play Game) expert, you are very fond of and familiar with many popular series of RPGs, and also have the same hobby with many other core players - collecting the treasures in every game you play. Most of the treasures are great equipments or fantastic troves, and they are usually placed in large labyrinths or hidden places. Recently the newest production of the greatest RPG -- Final Quest XXIV -- has just come out, and you've bought it yesterday at the first time, of course. However, after one night's challenge, even an expert like you also gave up because of the complex labyrinths in it. So you turned to the Internet and luckily found all the maps of labyrinths very soon. Although you don't know how those players got those maps so soon, the maps themselves are so detailed that they contain the positions and details of all enemies and treasures in all labyrinths, with them you can easily evaluate the time you need to defeat the enemies in each place and the time to walk from one place to another. Now you would like to know how long it will take you to pass each labyrinth at least, with all the treasures collected, of course.
For each labyrinth, the first line contains an integer N (1 <= N <= 500), the number of places (points) in the labyrinth. The next line contains N integers, each of which is the time you need to defeat the enemies in each place. The third line contains an integer T (0 <= T <= 500), the number of treasures in the labyrinth, and the next line are T integers, the indices of the places which contains treasure. There are at most fifteen different places which contain treasures. The fifth line contains an integer M (0 <= M <= N * (N - 1) / 2), the number of paths in the labyrinth, then following M lines with three integers, specifying the two ends of the paths and the time it will take you to pass. The last line contains two indices of the entrance and exit, respectively. All time are less than 32,768. The indices of places are from 1 to N, the paths are all bidirectional and distinct. All places in the labyrinths are reachable from the entrances, of course. The enemies you defeat will be reset once you leave the place. (Otherwise how can you get your level up?) We just assume that the increment of your level is too little to affect the time you need to defeat the enemies in every single labyrinth, and you won't lose out to any enemy as an expert and a good preparer.
There is an empty line between every two labyrinths, processing to the end of the file.
For each labyrinth, print the minimum time it will take you to pass the labyrinth with all treasures collected according to the map and the time you evaluated.
6 0 5 4 0 7 12 1 4 5 1 2 1 2 3 3 3 4 3 3 5 2 5 6 5 1 6
Author: XIAO, Dong
Source: ZOJ Monthly, May 2008