Problem F
Ticket to Ride
An assignment consists of a pair of cities that are to be connected by a series of shorter railway routes. A route can be claimed (for a certain cost associated with the route), but things are complicated by the fact that there is only a limited number of routes, and once a player claims a route, none of the other players can claim it. A player has successfully set up a train line between two cities if there is a path between the two cities using only routes that have been claimed by this player. For simplicity, we will ignore all additional aspects of the game (including the actual process of claiming routes and additional ways to score points).
For instance, if your assignment is to connect Stockholm and Amsterdam in the Figure above, you would probably want to claim the routes between Stockholm and Copenhagen, and between Copenhagen and Amsterdam. But if another player manages to claim the route between Copenhagen and Stockholm before you, your train line would have to use some other routes, e.g. by going to Copenhagen via Oslo.
In this problem, we will consider the rather bold strategy of trying to complete all four assignments (typically, this will be quite hard). As a preliminary assessment of the difficulty of achieving this, we would like to calculate the minimum cost of setting up all four lines assuming that none of the other players interfere with our plans. Your job is to write a program to determine this minimum cost.
Input
The input starts with two integers $1 \le n \le 40$, $0 \le m \le 1\, 000$, giving the number of cities and railway routes in the map, respectively. Then follow $n$ lines, giving the names of the $n$ cities. City names are at most $20$ characters long and consist solely of lower case letters (’a’-’z’).
After this follow $m$ lines, each containing the names of two different cities and an integer $1 \le c \le 10\, 000$, indicating that there is a railway route with cost $c$ between the two cities. Note that there may be several railway routes between the same pair of cities. You may assume that it is always possible to set up a train line from any city to any other city.
Finally, there are four lines, each containing the names of two cities, giving the four train line assignments.
Output
Output a single line containing a single integer, the minimum possible cost to set up all four train lines.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 15 stockholm amsterdam london berlin copenhagen oslo helsinki dublin reykjavik brussels oslo stockholm 415 stockholm helsinki 396 oslo london 1153 oslo copenhagen 485 stockholm copenhagen 522 copenhagen berlin 354 copenhagen amsterdam 622 helsinki berlin 1107 london amsterdam 356 berlin amsterdam 575 london dublin 463 reykjavik dublin 1498 reykjavik oslo 1748 london brussels 318 brussels amsterdam 173 stockholm amsterdam oslo london reykjavik dublin brussels helsinki |
3907 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 1 first second first second 10 first first first first second first first first |
10 |
Footnotes
- Ticket to Ride is copyrighted by Days of Wonder, Inc.
