A traveling salesman wants to survey N cities for business opportunities. The cities are numbered 0 through
N-1, and he wishes to visit each of them at least once. He starts at city 0 and can end at any city. There are several bidirectional roads, each connecting two different cities and costing some amount of money to traverse.
The traveling salesman also has a time machine. He can use the time machine to go back in time, without affecting which cities he is considered to have already visited. For example, suppose he has visited cities A, B, C, D, and E, in that order, and is currently
in city E. He can use the time machine to go back to city A, B, C, or D. Suppose he chooses to go back to city C. At that point, he can then go back further to city A or B, but he cannot use the time machine to go forward to city D or E. Note that going back
in time will not change the fact that he is considered to have already visited cities A, B, C, D, and E.
You are given the roads in the String[] roads. Concatenate the elements of
roads, in order, to get a single space-separated list of roads. Each road will be formatted "a,b,travelcost" (quotes for clarity), which means that the bidirectional road connects city a and city b, and costs travelcost to traverse.
He can use the time machine any number of times, and it costs nothing to use it. Return the minimum cost required to visit all the cities. Return -1 if it is impossible to visit all the cities. |
|
Definition
|
|
Class: |
TimeTravellingSalesman |
Method: |
determineCost |
Parameters: |
int, String[] |
Returns: |
long |
Method signature: |
long determineCost(int N, String[] roads) |
(be sure your method is public) |
|
|
|
|
Constraints
|
- |
N will be between 2 and 1000, inclusive. |
- |
roads will contain between 1 and 50 elements, inclusive. |
- |
Each element of roads will contain between 1 and 50 characters, inclusive. |
- |
Each character in roads will be '0'-'9', ',' or ' '. |
- |
roads will be formatted as described in the problem statement without leading or trailing spaces. |
- |
All integers in the concatenation of all the elements of
roads in the order they are given will have no extra leading zeroes. |
- |
In each road, a and b as described in the problem statement will be different and will each be between 0 and
N-1, inclusive. |
- |
In each road, travelcost as described in the problem statement will be between 1 and 10,000,000, inclusive. |
- |
For each two different cities, there will be at most one road connecting them. |
|
Examples
|
0) |
|
|
|
Returns: 2
|
Travel from city 0 to city 1. Go back in time to city 0. Travel from city 0 to city 2. The total cost is 1+1=2. |
|
|
1) |
|
|
6
|
{"0,1,2 1,4,2 4,3,3 2,4,4 0,5,3"}
|
|
Returns: 14
|
Travel from city 0 to city 1 to city 4 to city 3. Go back in time to city 4. Travel from city 4 to city 2. Go back in time to city 0. Travel from city 0 to city 5. The total cost is 2+2+3+4+3=14. |
|
|
2) |
|
|
|
Returns: -1
|
It is impossible to reach city 1. |
|
|
3) |
|
|
4
|
{"1,0",",10","0 2,1",",584 3,2",",754"}
|
|
Returns: 1438
|
|
相关推荐
topcoder-srm Topcoder SRM竞赛解决方案 测试是使用kawigi edit构建的。
你可以通过这道题去了解Topcoder的题目以及比赛形式
topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 , 1 <= K <= 1000.
关于TopCoder的竞赛指导,不仅仅是SRM,还有Bug Race、软件比赛的资料,是我从网上收集的,大部分是中文的
TopCoder SRM程序 我尝试过的TopCoder SRM程序列表。 在大多数时候,比赛时间与我的工作/其他活动冲突,因此我对TopCoder不太活跃。 但是我尽力去参加比赛,因为这很有趣。 就像在任何在线比赛中所期望的那样,代码...
topcoder-srm 顶级编码器srm问题集锦
用于topcoder的第3方编辑器插件。
Topcoder软件比赛注册方法和平台使用 Topcoder算法大赛客户端安装流程 Topcoder算法大赛客户端登陆及使用 Topcoder算法大赛注册流程 Topcoder图形比赛注册方法和平台使用
适合topcoder新手
topcoder算法讲座ppt
topcoder竞赛的算法讲座ppt
TopCoder比赛登录使用的客户端,需要配置Java环境
TopCoder新手入门指南,一步步操作既可以了,然后开启您的Topcoder编程之旅吧。
Topcoder的Java客户端,安装前确定已经安装了JRE
topcoder arena,包含ContestAppletProd.jnlp,CodeProcessor.jar,FileEdit.jar,TZTester,运行需要jre环境
TopCoper SmartWordToy problem 解决方法,C++源码。 Problem Statement The toy company "I Can't Believe It Works!...Form: http://community.topcoder.com/stat?c=problem_statement&pm=3935&rd=6532
topcoder的比赛作品,编译通过的。可以放心使用。
topcoder入门,对想做tc,但又不知道怎么搞的很有帮助,我首先也不知道搞。
给新手提供的TopCoder注册方法和平台使用 十分详细
概述当前,该集合具有以下代码: SRM(单回合)待办事项清单问题类别比赛类型比赛编号分配等级点表示法SRM 152 1个3 BiChromeSky SRM 655 1个3 排列计数SRM 656 1个2个叉车卡车操作员SRM 656 1个3 变形SRM 660 1个3 ...