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

0

acm之旅--最小成本排序

【问题描述】 　　现在通信公司需要在若干城市间（n）建立光纤通信网络连接(m)，为了节约成本需要在最节省费用的前提下建立通信网络，现用Kruskal算法求最小生成树。1 <= n < 26，1 <= m <= 100000。（不排除有重复边！） 【输入形式】 　　输入若干城市及部分城市间的距离，权值（距离）为int型； 　　输入的第一行正整数n表示顶点个数，接下来的n行是顶点名称（标识）；再接下来的一行为边的条数m，各条边（每条边）一行: 前2列为边的邻接点标号（顶点以字母顺序为序号，a为0），最后一列为边的权值，数值间以空格分隔。 【输出形式】 　最小生成树。输出格式参见样例输出。 【样例输入】 6 a b c d e f 10 0 1 2 0 2 31 0 3 22 0 4 13 0 5 8 1 2 29 2 4 20 4 5 26 3 5 15 　　1 3 17 【样例输出】 0 1 2 0 5 8 0 4 13 3 5 15 　　2 4 20

Spanning Tree --生成树    生成树是一种特殊通路，在实际应用中具有广泛意义。 比如：将道路网表示一个图，则生成树就表示从某地出发，到达所有其他各地且不绕圈子的直达路径，就是不经过同一条边两次（导航软件涉及这类算法）。    不同的遍历方法，可以从图得到不同的生成树，从不同顶点出发，也得到不同的生成树。但是，一个连通图的生成树一定是原图的极小连通子图，这包含原图所有顶点和 n

857. 雇佣 K 名工人的最低成本

leetCode1000. 合并石头的最低成本

1000. 合并石头的最低成本

LeetCode 雇佣K名工人的最低成本（优先队列）

GIS | 利用ARCGIS完成最小成本路径选择

PAT : 数据结构与算法题目集（中文）7-10 公路村村通
#include &amp;lt;iostream&amp;gt; #include &amp;lt;vector&amp;gt; #include &amp;lt;queue&amp;gt; #include &amp;lt;cstring&amp;gt; using namespace std; int UnionF[1001]; struct Heapstruct { int head, tail, value; }; bool Compare...

ArcGIS教程：创建成本最低路径

1月初工人数为10人，工人每月工作21天，每天工作8小时，按规定，工人每个月加班时间不得超过10个小时。1月初的库存量为200台。产品的销售价格为240元/件。该产品的销售特点是，如果当月的需求不能得到满足，顾客愿意等待该需求在后续的某个月内得到满足，但公司需要对产品的价格进行打折，可以用缺货损失来表示。6月末的库存为0（不允许缺货）。各种成本费用如表2所示。

Lingo与最小费用运输问题
Lingo与最小费用运输问题 代码如下： model: !6发点8 model: !6发点8收点运输问题; sets: warehouses/wh1..wh6/: capacity; vendors/v1..v8/: demand; links(warehouses,vendors): cost, volume; endsets min=@sum(links: ...

N 个任务分配给n 个人，任务j 分配给人i 的成本是C[i,j]，希望完成所有任 务的成本最低，算法如何设计？ 编程任务： 给定任务表示如下表，编程计算所需完成任务最低的成本。
ArcGIS应用分析--修建最小成本道路

15、合并石头的最低成本

2019独角兽企业重金招聘Python工程师标准&gt;&gt;&gt; ...

-

#include #include using namespace std; static const int MAX=1000; static const int VMAX=10000; int A[100],B[100],T[100]; bool V[100]; int solve(int N,int s) {     int ans=0;

LeetCode 使用最小花费爬楼梯

Think: 看了输入样例，目测是 最小生成树 问题。。而且还是模板题。。。既然是最小生成树问题，所以我就直接用了Prim算法。。初始化什么的还是老套路，直接写就可以了。。。因为最后在判断是否存在，所以也就是判断下ans是否存在就可以啦～！某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道

【图】最小生成树（最小成本）：Prim算法

7-10 公路村村通 （30 分) 最小生成树
7-10公路村村通（30分) 现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。 输出格式: ...
PAC成本方法

PTA 公路村村通 （30 分）
7-3 公路村村通 （30 分） 现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。 输出格式: 输出村村通需...
AStar 算法实例
A星算法 对于空地左键单击后会产生障碍，对障碍左键单击会消除障碍，对于起点，两次左键盘单击会消除起点，如果不存在起点，单击右键会产生起点，如果存在起点不存在终点，单击右键会产生终点，如果既存在起点又存在终点，单击右键会消除终点，点击开始寻路回画出路径
#先进先出#每批次采购价格不同，计算期末库存成本