设置所有四条线的最低成本,如何确定这个最低成本使用的是C语言的程序编写的代码算法策略的计算方式

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
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
acm之旅--最小成本排序
题目(7.7)链接: Minimum Cost Sort 思路:找交换的闭合回路,并且使用最小的元素作为交换媒介。当只移动闭合回路里的元素时,有成本函数 : ∑i=0nwi+(n−2)×min(wi)\sum_{i=0}^n w_{i}+(n-2) \times min(w_{i})∑i=0n​wi​+(n−2)×min(wi​)。 当需要使用闭合回路以外的元素作为交换媒介时,有成本函数 : s...
现在通信公司需要在若干城市间(n)建立光纤通信网络连接(m),为了节约成本需要在最节省费用的前提下建立通信网络,现用Kruskal算法求最小生成树
【问题描述】   现在通信公司需要在若干城市间(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
生成树和最小费用生成树以及Kruskal算法
Spanning Tree --生成树    生成树是一种特殊通路,在实际应用中具有广泛意义。 比如:将道路网表示一个图,则生成树就表示从某地出发,到达所有其他各地且不绕圈子的直达路径,就是不经过同一条边两次(导航软件涉及这类算法)。    不同的遍历方法,可以从图得到不同的生成树,从不同顶点出发,也得到不同的生成树。但是,一个连通图的生成树一定是原图的极小连通子图,这包含原图所有顶点和 n
畅通工程之最低成本建设问题(最小生成树(Kruskal)+并查集)
题目链接 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城镇间都可以实现快速交通(但不一定有直接的快速道路相连,只要互相间接通过快速路可达即可)。现得到城镇道路统计表,表中列出了有可能建设成快速路的若干条道路的成本,求畅通工程需要的最低成本。输入格式:输入的第一行给出城镇数目N (1<N≤1000)和候选道路数目M≤3N;随后的M行,
857. 雇佣 K 名工人的最低成本
有 N名工人。第i名工人的工作质量为quality[i],其最低期望工资为wage[i]。 现在我们想雇佣K名工人组成一个工资组。在雇佣一组 K 名工人时,我们必须按照下述规则向他们支付工资: 对工资组中的每名工人,应当按其工作质量与同组其他工人的工作质量的比例来支付工资。 工资组中的每名工人至少应当得到他们的最低期望工资。 返回组成一个满足上述条件的工资组至少需要多少...
leetCode1000. 合并石头的最低成本
有 N 堆石头排成一排,第 i 堆中有 stones[i] 块石头。 每次移动(move)需要将连续的 K 堆石头合并为一堆,而这个移动的成本为这 K 堆石头的总数。 找出把所有石头合并成一堆的最低成本。如果不可能,返回 -1 。 示例 1: 输入:stones = [3,2,4,1], K = 2 输出:20 解释: 从 [3, 2, 4, 1] 开始。 合并 [3, 2],成本为 5,剩下 [...
1000. 合并石头的最低成本
有 N 堆石头排成一排,第 i 堆中有stones[i]块石头。 每次移动(move)需要将连续的K堆石头合并为一堆,而这个移动的成本为这K堆石头的总数。 找出把所有石头合并成一堆的最低成本。如果不可能,返回 -1 。 示例 1: 输入:stones = [3,2,4,1], K = 2 输出:20 解释: 从 [3, 2, 4, 1] 开始。 合并 [3, 2],成本...
LeetCode 雇佣K名工人的最低成本(优先队列)
有 N 名工人。 第 i 名工人的工作质量为 quality[i] ,其最低期望工资为 wage[i] 。 现在我们想雇佣 K 名工人组成一个工资组。在雇佣 一组 K 名工人时,我们必须按照下述规则向他们支付工资: 对工资组中的每名工人,应当按其工作质量与同组其他工人的工作质量的比例来支付工资。 工资组中的每名工人至少应当得到他们的最低期望工资。 返回组成一个满足上述条件的工资组至少需要多少钱。 ...
GIS | 利用ARCGIS完成最小成本路径选择
利用已有的DEM数据,完成水文分析和表面分析,得到起点和终点之间的最小成本路径。 基本知识(参考ARCGIS HELP10.2) 成本距离 成本距离可以根据成本(例如,能量消耗、实施难度或安全性)进行衡量,并且行程成本可能随地形、地面覆盖物或其他因素而变化。 给定一组点,便可通过欧氏分配工具对点间的区域进行划分,这样,输出的每个区域均将包含最接近某给定点的所有区域。但是,如果点间行程成本因...
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...
遗传算法解决卡车货物运送成本最小C++
遗传算法解决卡车货物运送成本最小C++货物传送最优化算法:code.txt即为源代码.程序在VC6.0正常运行
ArcGIS教程:创建成本最低路径
成本路径工具用于确定目标点与源点之间的成本最低路径。除了需要指定目标外,成本路径工具还将用到通过成本距离工具得出的两个栅格:成本最低距离栅格和回溯链接栅格。这些栅格可通过成本距离工具或路径距离工具生成。回溯链接栅格可用于在成本距离表面上从目标沿最低成本路径回溯到源。
自动化测试的成本与收益
自动化测试主要形式 1.基于接口 2.基于UI 基于接口的自动化测试,主要是针对服务端逻辑的验证, 分为两种形式 1.各个接口独立测试,不涉及接口间的逻辑调用和数据共享,意在验证各个接口独立的功能是否正常 2.基于场景的接口测试,关注的是场景化,需要对业务流程有一定的熟悉程度,各个接口串联,实现某一个功能场景的验证。 基于UI的自动化测试,主要对模拟页面UI上的点击操作,验证输出结果...
若你是公司决策人员,请建立数学模型并制定出一个成本最低、利润最大的最优产销方案
1月初工人数为10人,工人每月工作21天,每天工作8小时,按规定,工人每个月加班时间不得超过10个小时。1月初的库存量为200台。产品的销售价格为240元/件。该产品的销售特点是,如果当月的需求不能得到满足,顾客愿意等待该需求在后续的某个月内得到满足,但公司需要对产品的价格进行打折,可以用缺货损失来表示。6月末的库存为0(不允许缺货)。各种成本费用如表2所示。
最小花费问题 (最短路径算法)
最小花费 题目描述     在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问A最少需要多少钱使得转账后B收到100元。 输入 第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。1 以下m行每行输入三个正整数x,y,z,表示标号为x的人和标号为y
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应用分析--修建最小成本道路
修建一条从学校通往目的地花费成本最低的道路。要求 1)新建路径成本较少; 2)新建路径为较短路径; 3)寻找最短路径的实现需要运用ArcGIS的空间分析(Spatial Analyst)中距离制图中的成本路径及最短路径、表面分析中的坡度计算及起伏度计算、重分类及栅格计算器等功能完成 4)最后提交寻找到的最短路径路线图 一 流程图二 具体步骤 2.1 提取坡度数据 在ArcToolbo
15、合并石头的最低成本
题目描述: 有 N 堆石头排成一排,第 i 堆中有 stones[i] 块石头。 每次移动(move)需要将连续的 K 堆石头合并为一堆,而这个移动的成本为这 K 堆石头的总数。 找出把所有石头合并成一堆的最低成本。如果不可能,返回 -1 。 示例 1: 输入:stones = [3,2,4,1], K = 2 输出:20 解释: 从 [3, 2, 4, 1] 开始。 合并 [3, 2],成本为 ...
存货成本确定方法-进价计算设计
2019独角兽企业重金招聘Python工程师标准&gt;&gt;&gt; ...
一个好的最低生存产品(MVP)是什么样子的?
一个成功的MVP的关键不是任何特定的特征或任何面向产品的特性。事实上,一个成功的MVP几乎总是不是很好。 MVP的目的 MVP的目的不是设计一些东西,然后测试它是否好。MVP的目的是尽可能快速地进行实验,以便了解产品在市场上取得成功的最终方向。你用MVP来做一个科学实验的目的是一样的:检验某种理论在现实世界中是否成立。但是你必须要小心,因为发布任何没有开发好的产品都会对你的业务造成损害。因此,...
证券公司4种常见的成本算法
-
最小成本排序
#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;  
快应用快速开发攻略和踩坑讲解
快应用是什么: 快应用是基于手机硬件平台的新型应用形态; 标准是由主流手机厂商组成的快应用联盟联合制定; 快应用标准的诞生将在研发接口、能力接入、开发者服务等层面建设标准平台;以平台化的生态模式对个人开发者和企业开发者全品类开放。 优势: 无需安装 即点即用-流畅; 能添加到桌面; 区别于原生App和WebApp; 超6亿流量扶持; 大势所趋。 存在问题: 需要申请九大厂商开发者账号,每个账号需要...
LeetCode 使用最小花费爬楼梯
数组的每个索引做为一个阶梯,第 i个阶梯对应着一个非负数的体力花费值 costi。 每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯。 您需要找到达到楼层顶部的最低花费。在开始时,你可以选择从索引为 0 或 1 的元素作为初始阶梯。 示例 1: 输入: cost = [10, 15, 20] 输出: 15 解释: 最低花费是从cost[1]开始,...
畅通工程之最低成本建设问题
Think: 看了输入样例,目测是 最小生成树 问题。。而且还是模板题。。。既然是最小生成树问题,所以我就直接用了Prim算法。。初始化什么的还是老套路,直接写就可以了。。。因为最后在判断是否存在,所以也就是判断下ans是否存在就可以啦~!某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城镇间都可以实现快速交通(但不一定有直接的快速道
天梯赛训练 畅通工程之局部最小花费问题(35 分)
习题8.5 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城镇间都可以实现快速交通(但不一定有直接的快速道路相连,只要互相间接通过快速路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建快速路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全地区畅通需要的最低成本。 输...
【图】最小生成树(最小成本):Prim算法
最小成本:nn 个顶点,用 n−1n-1 条边把一个连通图连接起来,并且使得权值的和最小。 最小生成树:构造连通网的最小代价生成树。 根据原来写的博客:【图】图的定义,里面提到一个连通图的生成树是一个极小连通子图,它含有图中全部的顶点,但只有足以构成一棵树的 n−1n-1 条边。 找连通网的最小生成树,经典的有两种算法:普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。先给出一个连通网
7-10 公路村村通 (30 分) 最小生成树
7-10公路村村通(30分) 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数N(≤1000)和候选道路数目M(≤3N);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。 输出格式: ...
PAC成本方法
欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来,用它写博客,将会带来全新的体验哦: Markdown和扩展Markdown简洁的语法 代码块高亮 图片链接和图片上传 LaTex数学公式 UML序列图和流程图 离线写博客 导入导出Markdown文件 丰富的快捷键 快捷键 加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl
关于基于成本定价的一些思考
问1:基于成本定价是怎么做的? 答1:1)背景:有些订单耗时长,成本高,但收取配送费少,这是不合理的。 2)难度定价逻辑:主要是对高成本订单加价,一方面,减少其单量,调整订单分布;另一方面,增加其配送费收入 3)难度定价方法:通过各种数据分析挖掘,定义一系列规则,通过仿真系统确定各规则权重,生成成本定义,从而在忙时对低客单价订单加价
村村通
题目描述 某市调查城镇交通状况,得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府“村村通工程”的目标是使全市任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要相互之间可达即可)。请你计算出最少还需要建设多少条道路? 输入输出格式 输入格式: 每个输入文件包含若干组测试测试数据,每组测试数据的第一行给出两个用空格隔开的正整数,分别是城镇数目N(N&amp;lt;1000)和...
合并石子(动态规划经典题)
步骤: 1. 设状态:f[i][j]表示从第i堆合并到第j堆,合并成一堆的最小得分 2. 初始状态:f[i][i]=0;     最终状态:f[1][n];//从第1堆合并到第n堆的最小得分 3.状态转移方程:f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);//s[i]表示前i堆石头数量总和 /* 7 13 7 8 16 21 4 1
PTA 公路村村通 (30 分)
7-3 公路村村通 (30 分) 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数N(≤1000)和候选道路数目M(≤3N);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。 输出格式: 输出村村通需...
AStar 算法实例
A星算法 对于空地左键单击后会产生障碍,对障碍左键单击会消除障碍,对于起点,两次左键盘单击会消除起点,如果不存在起点,单击右键会产生起点,如果存在起点不存在终点,单击右键会产生终点,如果既存在起点又存在终点,单击右键会消除终点,点击开始寻路回画出路径
#先进先出#每批次采购价格不同,计算期末库存成本
目的要求: 1.月末盘点了库存数量 2.配合上之前的采购单(采购量以及采购单价) 3.按照先进先出的准则 比如A产品,12月入库了三批各10个,价格分别为1元、2元、3元,12月出库了18个,月底库存剩下12(2个价格是2元,10个价格是3元)个,结存的库存成本应该是34元(2*2+10*3) 求助人想要的是以函数公式的方法达到如上效果,但是因为我的函数公式没有想到比较好的方法,所以我用VB...
简单C++程序的编写2:统计最高成绩和最低成绩
以下程序的功能是从键盘输入若干个学生的成绩,统计出最高成绩和最低成绩,当输入负数时,结束输入。 #include&amp;lt;iostream.h&amp;gt; void main() { int str[100],i,x,max,min; for(i=0;;i++) { cout&amp;lt;&amp;lt;&quot;please input:\n&quot;; cin&amp;gt;&amp;gt;x; if(x&amp;lt;0) ...
安卓网络请求框架对比
谷歌官网从安卓6.0系统开始默认不再支持httpClient,基于httpClient的框架建议不再使用 HttpClient 建议废弃 HttpUrlConnection 建议用框架 android-async-http框架 基于 httpClient,建议废弃 volley框架  集成AndroidAsyncHttp和ImageLoader框架的特点,a
动态规划:最优二分检索树
最优二分检索树 1、题目     设n=4,且(a1,a2,a3,a4)=(do,if,stop,then),设P(1:4)=(3,3,1,1),Q(0:4)=(1,3,2,1,1)(概率值“扩大”了16倍),求最优二分检索树   2、方法         动态规划。主要参考方法链接:http://www.cnblogs.com/stemon/p/3407773.html 主要用到
一种低成本八位嵌入式内核设计
微处理器八位内核设计,思路很新颖。一种比较实用简单的设计流程。希望对大家设计有帮助。

相似问题

0
DDI指标改写为MT4应用指标,求助大神帮忙看看这个程序改怎么写成MT4,尝试多次都编译失败
1
在vs2017+wdk10下如何编译编译出支持win2003/2008的驱动
1
C语言作品评分,去掉一个最低分和一个最高分,求平均值
1
for循环游泳比赛得分问题
1
卸载数据库时提示此计算机上的操作系统不符合SQL SERVER2012的最低要求
2
如何用c语言循环结构编写这个程序?
3
Oracle数据库中如何查询日期大于2018年3月1日的所有数据
1
MySql分组条件查询,非常急,折腾两天了,非常感谢。
2
当网页采用js动态获取数据时,HttpClient应如何获取数据?
1
C语言输入得分,去掉一个最高分一个最低分,计算平均分
1
随机森林分类应用在预测外汇涨跌上,我做的模型为啥精度这么奇怪,求大神给解释下
1
谁能帮我用java写一个用递归来从左下角到右上角走过一个数字矩阵,求走过的数字的最低和以及路径。
1
opencv在嵌入式设备上运行的最低ROM、RAM以及处理器速度的要求大概是怎样的?
0
程计算之。假设所有车辆到达关口的时刻都是整秒,运用C语言编写代码的过程去实现
1
学生成绩管理 C语言数据结构
2
C语言大佬求助;输入5个学生成绩,写一个函数,当主函数调用此函数后,能求出平均分、最高分和最低分
1
禅道的详细历史日志的实现思路?
0
关于servlet映射匹配原则优先级的问题
1
急需Hadoop结课作品,谢谢大家!!!
0
python小问题,求各位帮帮忙