1. 

/**
* FWP, Ausgew√¤hlte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 117 - The Postal Worker Rings Once
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=53
*
* @author Philippe Brousse
* @version 1.0, 10/23/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.112
*/
package postalworker;

import java.io.*;
import java.util.*;

/**
*
* @author Philippe Brousse
* @version 1.0
*/
public class Main
{

static Graph graph;

/**
* @param args
*/
public static void main(String... args) throws IOException
{
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
do
{
//TODO: Andere Speichermöglichkeit verwenden
//erste Stra√ĺe einlesen
String in = input.readLine().trim();
LinkedList<String> strassen = new LinkedList<String>();
graph = new Graph();

//Alle weiteren Stra√ĺen einlesen
do
{
//Strasse in die Strassenliste
strassen.add(in);
//Kreuzungen der Strasse
char von = in.charAt(0);
char nach = in.charAt(in.length() - 1);
//Strasse an Kreuzung 1...
if (!graph.contains(von))
{
//System.out.println("Neuer Knoten: " + von);
graph.add(new Node(von));
}
//Kein Check: jede Strasse hat eine einzigartige Kombination
//aus erstem und letztem Buchstaben!!!
//an den Knoten 'von' den Knoten 'nach' samt Kosten anh√¤ngen
//System.out.println("H√¤nge " + nach + " an " + von + " an");
graph.get(von).add(nach, in.length());

//...und 2 anh√¤ngen
if (!graph.contains(nach))
{
//System.out.println("Neuer Knoten: " + nach);

graph.add(new Node(nach));
}
//an den Knoten 'nach' den Knoten 'von' samt Kosten anh√¤ngen
//System.out.println("H√¤nge " + von + " an " + nach + " an");

graph.get(nach).add(von, in.length());

//n√¤chste Strasse
in = input.readLine().trim();
}
//hier: wenn deadend gelesen -> Ende, String wird verworfen
while (!in.equals("deadend"));
//besitzt der Graph einen Eulerkreis?
boolean eulerkreis = true;
//Speicher Knoten mit ungeradem Grad
Node[] odd = new Node[2];
int i = 0;
for (Node n : graph.nodes())
{

if (n.getNeighbours().keySet().size() % 2 == 1)
{
eulerkreis = false;
odd[i] = n;
i++;
}

}


int length = 0;
//Jede Strasse wird genau einmal passiert
for (String s : strassen)
{
length += s.length();
}
if (!eulerkreis)
{
//TODO: k√¼rzesten Weg von einem ungeraden Knoten zum Anderen finden -> Floyd-Warshall
//Summe der Grade aller Knoten positiv!!!! -> nicht 1 ungerader Knoten
Node start = odd[0];
Node end = odd[1];

Node nowAt = start;
start.setPathLength(0);
PriorityQueue<Node> open = new PriorityQueue<Node>();
open.offer(start);
while (!open.isEmpty())
{
nowAt = open.poll();
for (Node n : nowAt.getNeighbours().keySet())
{
int newPath = nowAt.pathLength + nowAt.getNeighbours().get(n);
if (n.pathLength > newPath)
{
n.setPathLength(newPath);
open.offer(n);
}
}

}
//Wegkosten errechnen:
length += graph.get(end).getPathLength();


// graph.get(odd[i]);
}
System.out.println(length);

}
//nichts mehr zu lesen -> Ende Programm
while (input.ready());
}

private static class Node implements Comparable<Node>
{

private final char name;
private final Map<Node, Integer> neighbours;
private int pathLength = Integer.MAX_VALUE;
private Node pred = null;

public Node getPred()
{
return pred;
}

public void setPred(Node pred)
{
this.pred = pred;
}

public int getPathLength()
{
return pathLength;
}

public void setPathLength(int pathLength)
{
this.pathLength = pathLength;
}

void add(char n, int costs)
{

if (graph.get(n) == null)
{
graph.add(new Node(n));
}
neighbours.put(graph.get(n), costs);
graph.get(n).getNeighbours().put(this, costs);
}

Node(char name)
{
this.name = name;
neighbours = new HashMap<Node, Integer>();
}

public char getName()
{
return name;
}

public Map<Node, Integer> getNeighbours()
{
return neighbours;
}

@Override
public int hashCode()
{
return (int) name;
}

@Override
public boolean equals(Object obj)
{
if (obj == null)
{
return false;
}
if (getClass() != obj.getClass())
{
return false;
}
final Node other = (Node) obj;
if (this.name != other.name)
{
return false;
}
return true;
}

@Override
public int compareTo(Node o)
{
return this.pathLength - o.getPathLength();
}

@Override
public String toString()
{
return "Node[" + name + "]";
}
}

private static class Graph
{

private final List<Node> nodes;

Graph()
{
nodes = new LinkedList<Node>();
}

boolean contains(char name)
{
return nodes.contains(new Node(name));
}

List<Node> nodes()
{
return nodes;
}

Node get(char name)
{
for (Node n : nodes)
{
if (n.getName() == name)
{
return n;
}
}
return null;
}

Node get(Node m)
{
return get(m.getName());
}

void add(Node n)
{
nodes.add(n);
}
}
}