Modified Travelling Salesperson ProblemProblem code: ENCD07 |
The problem involves determining a route for a SalesPerson so that he visits all the places while walking minimal distance, so as to rest weary legs. Given a sequence of streets (connecting given intersections) you are to write a program that determines the minimal cost tour that traverses every street at least once. The tour must begin and end at the same intersection. The cost of traversing a street is a function of the length of the street. In this problem the number of streets that meet at a given intersection is called the degree of the intersection. There will be at most two intersections with odd degree. All other intersections will have even degree, i.e., an even number of streets meeting at that intersection.
Input
The input consists of a sequence of one or more routes. A route is composed of a sequence of street names (strings), one per line, and is terminated by the string "end" which is NOT part of the route. The first and last letters of each street name specify the two intersections for that street, the length of the street name indicates the cost of traversing the street. All street names will consist of lowercase alphabetic characters. For example, the name abc indicates a street with intersections a and c of length 3, and the name computer indicates a street with intersections c and r of length 8. No street name will have the same first and last letter and there will be at most one street directly connecting any two intersections. As specified, the number of intersections with odd degree in a route will be at most two. In each route there will be a path between all intersections, i.e., the intersections are connected.
Output
For each route the output should consist of the cost of the minimal tour that visits all streets at least once. The minimal tour costs should be output in the order corresponding to the input routes.
Example
Input: one two three end mat dzrtmouth limkoping takmania yolk emary comnell duce kamnas hifdesheim comcord arcansas wildiams glafgow end Output: 11 114
| Author: | rscrbv |
| Date Added: | 19-01-2010 |
| Time Limit: | 4 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
How we can know intput
How we can know intput terminates here ?
EOF character ?
Every input terminates with