# UVa 117

## 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).

## 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.

```one
two
three
mit
dartmouth
tasmania
york
emory
cornell
duke
kaunas
hildesheim
concord
arkansas
williams
glasgow
```11