UVa 117
From Algorithmist
Contents |
[edit] 117 - The Postal Worker Rings Once
[edit] Summary
This problem reduces to a Graph, by looking at each first or last character as a vertex, and the street name as an edge. We can reduce this problem to a Eulerian Path or a Eulerian Cycle problem, since each vertex will have an even number of degrees (except for at most 2 vertices).
[edit] Explanation
Even though at first glance, it seems like it might need the Chinese Postman algorithm, but since each vertex will have an even number of degrees (except for at most 2 vertices), we can use the simplier Eulerian Path/Eulerian Cycle algorithm instead. If all vertices are of even degrees, then you're done, since the solution is simply the Eulerian Cycle - the sum of the weights of all the edges. Otherwise, we will have to calculate the Eulerian Path, then you will have to find the shortest path between the two odd-degree vertices. This can be done with any of the Shortest Path algorithms.
[edit] Input
one two three deadend mit dartmouth linkoping tasmania york emory cornell duke kaunas hildesheim concord arkansas williams glasgow deadend
[edit] Output
11 114
