Ticket to Ride

Problem Description
Ticket to Ride is a board game for up to 5 players. The goal of the game is to set up train lines (and to thwart the opponents’ attempts at setting up their train lines). At the beginning of play, each player is assigned four train lines. A player may choose to discard as many of these four assignments as she likes. Each assignment has a score, corresponding to its difficulty (so, typically, a train line between e.g. Stockholm and Tokyo would be worth more than a train line between e.g. Stockholm and Utrecht). At the end of the game, each player gets points for the assignments that they have successfully completed, and penalty points for the assignments that they have failed to complete.

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 consists of several (at most 20) games to be analyzed. Each game starts with two integers 1 <= n <= 30, 0 <= m <= 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 <= c <= 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 will be four lines, each containing the names of two cities, giving the four train line assignments.

The input is terminated by a case where n = m = 0. This case should not be processed.

Output
For each game, output a single line containing a single integer, the minimum possible cost to set up all four train lines.

Sample Input
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
2 1
first
second
first second 10
first first
first first
second first
first first
0 0

Sample Output
3907
10

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
设置所有四条线的最低成本,如何确定这个最低成本使用的是C语言的程序编写的代码算法策略的计算方式
-
Lucky Ticket
-
Puncher 代码求设计
-
Banal Tickets 怎么写代码,不会回答的请绕道
-
Fred's Lotto Tickets C语言,会的来回答
-
Puncher 程序实现方法
-
微信开发周边接口 ticket无效问题
-
谁能帮我分下一下代码的内存变化,最好能画一张简略的JVM
-
java中如何获取微信的jsapi_ticket
-
Boatherds 程序的做法
-
Get-Together at Stockholm程序编程怎么做的
-
从后端接数据,number类型的数据,后面的无效0被自动舍掉了
-
单点登录拿到ticket之后怎么做
-
火车购票问题的一个解决思路,Train Tickets
-
Mileage Bank 怎么来实现的
-
如何用C语言实现一个手机号一天只能投一次票?
-
Let's Go to the Movies
-
小白提问:请问我的代码步骤哪里出错了
-
程序员真是太太太太太有趣了!!!
网络上虽然已经有了很多关于程序员的话题,但大部分人对这个群体还是很陌生。我们在谈论程序员的时候,究竟该聊些什么呢?各位程序员大佬们,请让我听到你们的声音!不管你是前端开发...
史上最详细的IDEA优雅整合Maven+SSM框架(详细思路+附带源码)
网上很多整合SSM博客文章并不能让初探ssm的同学